777. Swap Adjacent in LR String 的数学推导

https://leetcode.com/problems/sw ... string/description/
L和R只能借助X向左或者向右移动，L向左移动时不能跨过R，（因为如果L左边是R的时候，没法向左移动），R向右也不能跨过L

Start可以move到End
=>

推论1：除去X后，R和L的相对位置在初始和最终状态不变。
推论2：L只能向左移动，所以最终状态L的index，必须<=初始时L的index
             R只能向右移动，所以最终状态R的index，必须>=初始时R的index
推论3：初始和结束字符串长度相等


怎么证明推论1，2，3是 Start可以move到End的充分条件？也就是=>反过来也成立？

大神的这段证明有看懂的吗：
This shows being solid and accessible are necessary conditions. With an induction on the number of people, we can show that they are sufficient conditions. The basic idea of the proof is this: A person on the end either walks away from the others, or walks towards. If they walk away, then let them walk first and it is true; if they walk towards, then let them walk last and it is true (by virtue of the target being solid).

自己顶 字数字数字数

可以用数学归纳法进行构造性证明，首先明确要证明的内容：
定理1：对于任意长度的两个字符串A和B，如果推论1/2/3同时成立，那么存在从A到B的移动序列S。

(这里所定义的移动序列里面每个元素都是“将第m个L左移(R右移)一格”这种格式。)

现在，给定推论1/2/3成立，不妨设字符串中L/R的总数量为n，我们对n进行归纳：

Base case:
n = 1，易证。

Inductive step:
设当n = k时，定理1成立。

考虑n = k + 1，我们先做如下操作：将A和B各自最左边一个非X字符替换为X，记替换后的字符串分别为A'，B'。
易证A'和B'满足推论1/2/3，由归纳假设可知存在A'到B'的移动序列，记为S'。

现在我们来构造A到B的移动序列S，考虑所替换的最左边的字符，两种情况：
Case 1, L
首先移动A中最左边的L到B中最左边L的位置，易证这一移动序列是可行的（因为是将A的最左边的字符向左移动）。然后，对A应用移动序列S'，易证S'不会触碰到最左边的L，所以也是可行的。

Case 2, R
首先对A应用变换序列S'，同样易证S'不会触碰到最左边的R，然后移动A中最左边的R到B中最左边R的位置。

这样我们就构造出了一个可行的移动序列S，也就证明了定理1对任意n都是成立的。
(而且这个证明其实就是上面那段英文所说的内容。)

你的问题是啥。？ 一定能从start 走到end 然后 end 走回start 的条件么？

这三个推论不能算推论吧， 是显然成立的fact。



L向左移动时不能跨过R，R向右也不能跨过L -》 推论1显然

L 只能向左， R 只能向右 -》 推论2显然

字符串长度不等 | L R 的个数不等 -》不是一个字符串， 推论3显然

从start 到 end你可以考虑L 跟 R的位置状态， 一共就这么多个状态。 那R 跟 L可以去的位置也没有很多。。因为都是单向行驶。

这个题我最开始以为LX 跟 XL 可以互换， 然后 XR 跟RX也可以互换。鬼鬼， 这样才有意思点。。

magicsets 发表于 2018-6-27 17:05
可以用数学归纳法进行构造性证明，首先明确要证明的内容：
定理1：对于任意长度的两个字符串A和B，如果推 ...

楼主比较愚钝，再看你的数学归纳法证明，就好像比较容易理解了。
如果假设开始时没有L或者R，都是X。假设End字符串已知，反过来想怎么一步步在满足3个条件的情况下，插入L和R使得形成的Start字符串可以移动到End。
谢谢！

顶！d=====(￣▽￣*)b