https://leetcode.com/problems/swap-adjacent-in-lr-string/
http://www.programmersought.com/article/724530505/
https://xingxingpark.com/Leetcode-777-Swap-Adjacent-in-LR-String/
X.
下面这种解法也挺巧妙的，这里我们使用两个计数器cntL和cntR，分别来统计L和R出现的次数，统计方法时，start中出现了L或R，计数器自增1，end中出现了L或R，计数器自减1。注意我们检测的顺序很重要，由于start中的R必须在end中的R前面，所以我们要先检测start中的R，同理，由于end中的L必须要在start中的L前面，所以我们要先检测end中的L，那么四个if写完后，如果cntL或者cntR中有任何一个小于0了，说明限制条件被打破了，返回false，或者当二者都大于0的时候，说明此时不匹配了，参见上面解法中对于去掉所有的X的解释，一个道理，说明L和R的相对顺序不同了，那么也是false。最终for循环退出后，如果cntL和cntR均为0的时候，才返回true，否则就是false
X. Proof
https://www.1point3acres.com/bbs/thread-431706-1-1.html
推论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都是成立的。
(而且这个证明其实就是上面那段英文所说的内容。)
如果假设开始时没有L或者R，都是X。假设End字符串已知，反过来想怎么一步步在满足3个条件的情况下，插入L和R使得形成的Start字符串可以移动到End。
In a string composed of
'L', 'R', and 'X' characters, like "RXXLRXRXL", a move consists of either replacing one occurrence of "XL" with "LX", or replacing one occurrence of "RX" with "XR". Given the starting string start and the ending string end, return True if and only if there exists a sequence of moves to transform one string to the other.
Example:
Input: start = "RXXLRXRXL", end = "XRLXXRRLX" Output: True Explanation: We can transform start to end following these steps: RXXLRXRXL -> XRXLRXRXL -> XRLXRXRXL -> XRLXXRRXL -> XRLXXRRLX
Note:
1 <= len(start) = len(end) <= 10000.- Both start and end will only consist of characters in
{'L', 'R', 'X'}.
http://www.programmersought.com/article/724530505/
IQ question
Originally thought to be a search problem similar to the maze, seeing the size of the data is so large, it does not feel like, look at the tag really is an IQ problem, then I gave up, IQ is not enough.
The topic says that you can change the XL in the initial string to LX. You can replace the RX in the initial string with XR, which means that the L in the initial string can only be moved to the left. In the initial string, R can only move to the right. And L and R are impossible to exchange the order, the number of L and R corresponding to the two strings should be equal. Once you know this rule, just use the double pointer to solve it.
Use i, j to point to the starting position of start and end respectively. If they point to X, then move to the right to a position other than X, then the characters they point to should be equal, otherwise return False. If it points to L, then the index of L in start must be smaller than the index of L in end; if it points to R, then the index of R in end must be larger than the index of R in end. It is necessary to move i and j backwards at the same time before the end of the while.
Returns True after all judgments are completed.
The time complexity is O(N) and the space complexity is O(1).
http://www.cnblogs.com/grandyang/p/9001474.html
这道题给了我们一个只含有L，R，X三个字符的字符串，然后说有两种操作，一种是把 "XL" 变成 "LX"，另一种是把 "RX" 变成 "XR"。博主刚开始没有读题意，以为二者是可以互换的，错误的认为认为 "LX" 也能变成 "XL"，其实题目这种变换是单向，这种单向关系就是解题的关键，具体来说，就是要把start字符串变成end字符串的话，L只能往前移动，因为是把 "XL" 变成 "LX"，同样，R只能往后移动，因为是把 "RX" 变成 "XR"。题目给的那个例子并不能很好的说明问题，博主之前那种双向变换的错误认知会跪在这个例子：
start = "XXRXXLXXXX"
end = "XXXXRXXLXX"
end = "XXXXRXXLXX"
我们观察这个test case，可以发现start中的R可以往后移动，没有问题，但是start中的L永远无法变到end中L的位置，因为L只能往前移。这道题被归类为brainteaser，估计就是因为要观察出这个规律吧。那么搞明白这个以后，我们其实可以用双指针来解题，思路是，我们每次分别找到start和end中非X的字符，如果二者不相同的话，直接返回false，想想问什么？这是因为不论是L还是R，其只能跟X交换位置，L和R之间是不能改变相对顺序的，所以如果分别将start和end中所有的X去掉后的字符串不相等的话，那么就永远无法让start和end相等了。这个判断完之后，就来验证L只能前移，R只能后移这个限制条件吧，当i指向start中的L时，那么j指向end中的L必须要在前面，所以如果i小于j的话，就不对了，同理，当i指向start中的R，那么j指向end中的R必须在后面，所以i大于j就是错的，最后别忘了i和j同时要自增1，不然死循环了
bool canTransform(string start, string end) { int n = start.size(), i = 0, j = 0; while (i < n && j < n) { while (i < n && start[i] == 'X') ++i; while (j < n && end[j] == 'X') ++j; if (start[i] != end[j]) return false; if ((start[i] == 'L' && i < j) || (start[i] == 'R' && i > j)) return false; ++i; ++j; } return true; }
给出了两种变换的规则，从“XL”到“LX”和从“RX”到“XR”。所以我们可以给出两条规律：
- 如果start能变换到end，那么除去两个字符串中的
"X"，剩余的字符串一定相同。因为任意"R"和"L"的相对顺序都不会发生变化，我们定义出去"X"的字符串为有效字符串 - 根据变换的规则，
"L"不能向右移，“R”不能向左移，所以 start 中“L”对应的 index"i"一定不小于 end 中“L”对应的index"j"；start 中“R”对应的 index"i"一定不大于 end 中“R”对应的index"j"；- i >= j, 如果 start[i]==end[j]==”L”
- i <= j, 如果 start[i]==end[j]==”R”
X.
下面这种解法也挺巧妙的，这里我们使用两个计数器cntL和cntR，分别来统计L和R出现的次数，统计方法时，start中出现了L或R，计数器自增1，end中出现了L或R，计数器自减1。注意我们检测的顺序很重要，由于start中的R必须在end中的R前面，所以我们要先检测start中的R，同理，由于end中的L必须要在start中的L前面，所以我们要先检测end中的L，那么四个if写完后，如果cntL或者cntR中有任何一个小于0了，说明限制条件被打破了，返回false，或者当二者都大于0的时候，说明此时不匹配了，参见上面解法中对于去掉所有的X的解释，一个道理，说明L和R的相对顺序不同了，那么也是false。最终for循环退出后，如果cntL和cntR均为0的时候，才返回true，否则就是false
bool canTransform(string start, string end) { int n = start.size(), cntL = 0, cntR = 0; for (int i = 0; i < n; ++i) { if (start[i] == 'R') ++cntR; if (end[i] == 'L') ++cntL; if (start[i] == 'L') --cntL; if (end[i] == 'R') --cntR; if (cntL < 0 || cntR < 0 || cntL * cntR != 0) return false; } return cntL == 0 && cntR == 0; }
https://medium.com/@ChYuan/leetcode-no-777-swap-adjacent-in-lr-string-%E5%BF%83%E5%BE%97-medium-748be5d19c36
一開始我以為是互換都可以，覺得很困難，但是再仔細看題目，其實是只有兩種換的方式，再好好的分析，會發現其實可以不用管 "X"，把換的方式想成 L 只能往左移，R 只能往右移 (並且碰到 L or R 就不能再移動了)。
如果要合法，就有四個要求要做到:
(1) 全部字串長度相等
(2) 去掉 X 後的字串要相等
(3) 因為 L只能往左移，所以原本字串和後來字串的 L 關係就是原本字串的 L 一定不能比後來字串的 L 早出現。
(4) R 以此類推
一開始我以為是互換都可以，覺得很困難，但是再仔細看題目，其實是只有兩種換的方式，再好好的分析，會發現其實可以不用管 "X"，把換的方式想成 L 只能往左移，R 只能往右移 (並且碰到 L or R 就不能再移動了)。
如果要合法，就有四個要求要做到:
(1) 全部字串長度相等
(2) 去掉 X 後的字串要相等
(3) 因為 L只能往左移，所以原本字串和後來字串的 L 關係就是原本字串的 L 一定不能比後來字串的 L 早出現。
(4) R 以此類推
X. Stack
我覺得這種題目，要是跟你說 swap 規則一定不是用 swap 去解
一開始真的嘗試用暴力法(BFS)去遞迴，馬上就超過時間限制
public boolean canTransform(String start, String end) {
ArrayList<Character> array = new ArrayList<Character>();
start = start.replaceAll("\"", "").replace("\\", "").replace("\\", "");
end = end.replaceAll("\"", "").replace("\\", "").replace("\\", "");
String rl_start = start.replaceAll("X", "");
String rl_end = end.replaceAll("X", "");
if (!rl_start.equals(rl_end)) { return false; }
if (start.length() != end.length()) { return false; }
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < start.length(); i++) {
if (start.charAt(i) == 'R') { stack.push(start.charAt(i)); }
if (end.charAt(i) == 'R') {
if (stack.empty()) {
return false;
} else {
stack.pop();
}
}
}
stack = new Stack<Character>();
for (int i = 0; i < start.length(); i++) {
if (end.charAt(i) == 'L') { stack.push(end.charAt(i)); }
if (start.charAt(i) == 'L') {
if (stack.empty()) {
return false;
} else {
stack.pop();
}
}
}
return true;
}
def canTransform(self, start, end):
"""
:type start: str
:type end: str
:rtype: bool
"""
N = len(start)
sR = eR = sL = eL = 0
for x in range(N):
if start[x] == 'R': sR += 1
if end[x] == 'R': eR += 1
if sR < eR: return False
if sR != eR: return False
for x in range(N - 1, -1, -1):
if start[x] == 'L': sL += 1
if end[x] == 'L': eL += 1
if sL < eL: return False
if sL != eL: return False
start, end = start.replace('X', ''), end.replace('X', '')
return start.split('R') == end.split('R')
X. https://leetcode.com/problems/swap-adjacent-in-lr-string/discuss/113782/Python-simple-solution-3-lines-O(n)
The idea it to compare 'L' position in start is greater than or equal to that in end, also 'R' position in start is less than or equal to that in end.
The reason is 'L' can move left when 'X' exists before, and 'R' can move right when 'X' exists after, and 'L' and 'R' cannot cross each other, so we do not care about 'X'.
class Solution:
def canTransform(self, start, end):
"""
:type start: str
:type end: str
:rtype: bool
"""
s = [(c, i) for i, c in enumerate(start) if c == 'L' or c == 'R']
e = [(c, i) for i, c in enumerate(end) if c == 'L' or c == 'R']
return len(s) == len(e) and all(c1 == c2 and (i1 >= i2 and c1 == 'L' or i1 <= i2 and c1 == 'R') for (c1, i1), (c2, i2) in zip(s,e))X. Proof
https://www.1point3acres.com/bbs/thread-431706-1-1.html
推论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都是成立的。
(而且这个证明其实就是上面那段英文所说的内容。)
如果假设开始时没有L或者R，都是X。假设End字符串已知，反过来想怎么一步步在满足3个条件的情况下，插入L和R使得形成的Start字符串可以移动到End。
