777. Swap Adjacent in LR String (Medium)
https://leetcode.com/problems/swap-adjacent-in-lr-string/
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'}
.
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);
}
}