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. 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);
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:18

results matching ""

    No results matching ""