777 Swap Adjacent in LR String

777. Swap Adjacent in LR String

1. Question

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 stringstartand the ending stringend, returnTrueif 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'}.

2. Implementation

(1) Two Pointers

class Solution {
    public boolean canTransform(String start, String end) {
        if (start.length() != end.length()) {
            return false;
        } 

        int countX1 = 0, countX2 = 0;
        int index1 = 0, index2 = 0;

        while (index1 < start.length() && index2 < end.length()) {
            // Get the first non x character in start string, and count the number of X 
            while (index1 < start.length() && start.charAt(index1) == 'X') {
                ++countX1;
                ++index1;
            }

            // Get the first non x character in end string, and count the number of X
            while (index2 < end.length() && end.charAt(index2) == 'X') {
                ++countX2;
                ++index2;
            }

            // Both strings get to the end, return true;
            if (index1 == start.length() && index2 == end.length()) {
                return true;
            }
            // One of the string is running out of character, return false;
            else if (index1 == start.length() || index2 == end.length()) {
                return false;
            }
            // If the first non x character are different, since L will only get to left, and R can only get to right,
            // there is no way for start string to be transformed into end string
            else if (start.charAt(index1) != end.charAt(index2)) {
                return false;
            }
            // L can only get to left, if number of x in start is less than number of x in end string, it is impossible for e
            // start string to be transformed into end string
            else if (start.charAt(index1) == 'L' && countX1 < countX2) {
                return false;
            }
            // R can only get tor right, if number of x in start is greater than the number of x in end string, it is impossible 
            // start string to be transformed into end string
            else if (start.charAt(index1) == 'R' && countX1 > countX2) {
                return false;
            }
            else {
                ++index1;
                ++index2;
            }
        }
        return true;
    }
}

3. Time & Space Complexity

Two Pointers: 时间复杂度O(n), 空间复杂度O(1)