406. Queue Reconstruction by Height
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 1
Input: start = "X", end = "L"
Output: false
Explanation:
We can transform start to end following these steps:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX
Example 2
Input: start = "LLR", end = "RRL"
Output: false
题意： 这道题是主要是观察规律，从替换的规则上面来看， R 只能和 X 向右换，而 L 只能和 X 向左换。 并且通过这个规律，可以知道 R 和 L 的相对位置不会发生变化。 因次，我们对比原始串和目标串的时候， 可以忽律 X 的位置，然后一一对比顺续是否一致即可。 中间需要注意的是因为 L 只能向左移动， 那么如果发现目标串里面的 L 的位置在其之后返回 false。 对 R 同理。
代码
class Solution {
public boolean canTransform(String start, String end) {
int n = start.length();
int i = 0, j = 0;
while(i < n || j < n) {
while(i < n && start.charAt(i) == 'X') i++;
while(j < n && end.charAt(j) == 'X') j++;
if(i == n && j == n) return true;
if(i ==n || j == n) return false;
if(start.charAt(i) != end.charAt(j)) return false;
if(start.charAt(i) == 'L' && i < j) return false;
if(start.charAt(i) == 'R' && i > j) return false;
i++;j++;
}
return true;
}
}