777. Swap Adjacent in LR String

ref:

Loading...LeetCode

ref:

https://www.cnblogs.com/grandyang/p/9001474.html

two pointers

T: O(n)
S: O(1)

class Solution {
    public boolean canTransform(String start, String end) {
         // remove X, start and end should the same
        if (!start.replace("X", "").equals(end.replace("X", ""))) {
            return false;
        }
        
        int n = start.length();
        int sIdx = 0;
        int eIdx = 0;
        while (sIdx < n && eIdx < n) {
            // 遇到 'X' 略過
            while (sIdx < n && start.charAt(sIdx) == 'X') {
                sIdx++;
            }
            while (eIdx < n && end.charAt(eIdx) == 'X') {
                eIdx++;
            }

            // 可能前面 while 最後跳出時剛好在 n
            if (sIdx == n && eIdx == n) { //代表跑完了
                return true;
            }
            if (sIdx == n || eIdx == n) { //一長一短, 一定錯
                return false;
            }
            
            char s = start.charAt(sIdx);
            char e = end.charAt(eIdx); 
            if (s != e) { // 照理去掉 X 後, start end 指向同一個字
                return false;
            }
            if (s == 'L' && eIdx > sIdx) { // check 位置, Ｌ eidx 應該會越來越小
                return false;
            }
            if (s == 'R' && eIdx < sIdx) { // check 位置, Ｌ eidx 應該會越來越大
                return false;
            }
            
            sIdx++;
            eIdx++;
        }
        return true;
        
    }
    
}

/*
1.
"XL" with "LX", or replacing one occurrence of 
"RX" with "XR"

"XL" with "LX" => we can get L will continuously move to left
"RX" with "XR" => we can get R will continuously move to right

2.
so in correct case, after swaping, R shoud in right side (end index > start index)
RXXLRXRXL (start index: 0)
p
XRLXXRRLX (end index: 1)
 p
and after change, the start[start index] == end[end index] => start[0] == end[1] == R

3.
so in correct case, after swaping, L shoud in left side (end index < start index)
RXXLRXRXL (start index: 3)
   p
XRLXXRRLX (end index: 2)
  p

and after change, the start[start index] == end[end index] => start[3] == end[2] == L
 
4.
one more noticed!
remove X, they should the same
"RXXLRXRXL" => RLRRL
"XRLXXRRLX" => RLRRL
一開始的判斷
if (!start.replace("X", "").equals(end.replace("X", ""))) {
    return false;



T: O(n)
S: O(1)
*/