头脑风暴

Swap Adjacent in LR String

• 给定2个string, start and end, 只包含L, X, R char

• 可以replace "XL" with "LX", replace "RX" with "XR", 求问start 是否能transform成end string

• 一开始自然的想到了word ladder的思路，给定source and dest求问最短路径

• 暴力写了个BFS结果TLE了

  • start: "XXRXXXXXXXRXRXXXLXXLXXLXXXXXRXXXXXXXXLXX"

  • end: "XXXRXXXXRXXXXXXRXXXLXXXXXXXLXXLXXRXXLXXX"

class Solution {
    public boolean canTransform(String start, String end) {
        if (start.equals(end)) return true;
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.offer(start);
        visited.add(start);
        while (!queue.isEmpty()) {
            String cur = queue.poll();
            for (int i = 0; i < cur.length() - 1; i++) {
                if (cur.substring(i, i + 2).equals("XL")) {
                    String next = cur.substring(0, i) + "LX" + cur.substring(i + 2);
                    if (next.equals(end)) return true;
                    if (visited.contains(next)) continue;
                    queue.offer(next);
                    visited.add(next);
                }
                if (cur.substring(i, i + 2).equals("RX")) {
                    String next = cur.substring(0, i) + "XR" + cur.substring(i + 2);
                    if (next.equals(end)) return true;
                    if (visited.contains(next)) continue;
                    queue.offer(next);
                    visited.add(next);
                }
            }
        }
        return false;
    }
}

• 然后就去Discuss里看了其它答案，发现这题是个数学推演题

• since we can only move R to the right RX->XR, move L to the left, XL->LX L and R can never cross each other

• just skip X character and compare position of L and R in 2 strings

• for start[i] = end[j] = L, check i>=j, 因为 L只能左移

• start[i] = end[j] = R, check i<=j， 因为R只能右移

• 转换成了two pointer

• 这里有个非常tricky的case

  • start:"XXRXLXRXXX"

  • end: "XXRLXXXXXR"

• 因为end的最后一个char是R, 但是start最后一个R之后还有一堆X, 所以不能简单的写while (p1 < n && p2 < n), 需要特殊处理p1==n和p2==n的情况

class Solution {
    public boolean canTransform(String start, String end) {
        if (start.length() != end.length()) return false;
        int n = start.length();
        int p1 = 0, p2 = 0;
        while (p1 <= n && p2 <= n) {
            while (p1 < n && start.charAt(p1) == 'X') p1++;
            while (p2 < n && end.charAt(p2) == 'X') p2++;
            if (p1 == n && p2 == n) return true;
            if (p1 == n) {
                while (p2 < n && end.charAt(p2) == 'X') p2++;
                return p2 == n;
            }
            if (p2 == n) {
                while (p1 < n && start.charAt(p1) == 'X') p1++;
                return p1 == n;
            }
            if (start.charAt(p1) != end.charAt(p2)) return false;
            if (start.charAt(p1) == 'L' && p1 < p2) return false;
            if (start.charAt(p1) == 'R' && p1 > p2) return false;
            p1++;
            p2++;
        }
        return p1 == n && p2 == n;
    }
}