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'}.

Hints

Solutions

https://blog.csdn.net/huanghanqian/article/details/79255301

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

    public boolean helper(char[] start, char[] end, int low, int high) {
        if (low > high) {
            return true;
        }
        if (low == high) {
            return false;
        }
        while (low <= high && start[low] == end[low]) {
            low++;
        }
        if (low < high) {
            int i=-1;
            for (i = low; i < high; i++) {
                if (start[i] == 'X' && start[i + 1] == 'L') {
                    start[i]='L';
                    start[i+1]='X';
                    break;
                } else if (start[i] == 'R' && start[i + 1] == 'X') {
                    start[i]='X';
                    start[i+1]='R';
                    break;
                }
            }
            if(i==high){
                return false;
            }
        }
        return helper(start, end, low, high);
    }
}
Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-04-09 12:23:14

results matching ""

    No results matching ""