# 777. Swap Adjacent in LR String (Medium)

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. `1 <= len(start) = len(end) <= 10000`.
2. Both start and end will only consist of characters in `{'L', 'R', 'X'}`.

## Solutions

``````class Solution {
// This problems is too complicated, you even cannot imagine its corner cases
public boolean canTransform(String start, String end) {
if (start.length() != end.length()) {
return false;
}

return recursion(start.toCharArray(), end.toCharArray(), 0, start.length() - 1);
}

public boolean recursion(char[] start, char[] end, int low, int high) {
while (low <= high && start[low] == end[low]) {
low++;
}

// means every bit are identical
if (low > high) {
return true;
}

// means only the last bit is different, no chance for changing
if (low == high) {
return false;
}

// Through bitwise comparision, start and end differ from position low

// Assume start[low:high]='LLRRXXXX', move the closest X forward. And in later recursion,
// Continue this process until make it to the head and couple with the first L as pair

int i;
for (i = low; i < high; i++) {
if (start[i] == 'X' && start[i + 1] == 'L') {
start[i] = 'L';
start[i + 1] = 'X';
break;
}

if (start[i] == 'R' && start[i + 1] == 'X') {
start[i] = 'X';
start[i + 1] = 'R';
break;
}
}

// Neither patterns XL or RX are present.

// Since at the beginning we have examined start and end is not identical,
// plus no replacement takes place at above code, we can conclude
// X,L,R in start[low:high] cannot perfectly pairs. So return false.

if (i == high) {
return false;
}

// We will find that low is not changed when conducting swap operations.

return recursion(start, end, low, high);
}
}
``````