SwapAdjacentInLRString [source code]


public class SwapAdjacentInLRString {
static
/******************************************************************************/
class Solution {
    public boolean canTransform(String start, String end) {
        if (start.length () != end.length ())
            return false;
        char[] chs = start.toCharArray (), che = end.toCharArray ();
        int i = 0, j = 0;
        while (i < chs.length && j < che.length) {
            while (i < chs.length && chs[i] == 'X')
                i++;
            while (j < che.length && che[j] == 'X')
                j++;
            if ((i < chs.length) ^ (j < che.length))
                return false;
            if (i < chs.length && j < che.length) {
                if (chs[i] != che[j])
                    return false;
                if (chs[i] == 'L' && i < j)
                    return false;
                if (chs[i] == 'R' && i > j)
                    return false;
            }
            i++;
            j++;
        }
        return true;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        SwapAdjacentInLRString.Solution tester = new SwapAdjacentInLRString.Solution();
        String[] inputs = {
            "RXXLRXRXL", "XRLXXRRLX", "true",
            "X", "L", "false",
            "XXRXXLXXXX", "XXXXRXXLXX", "false",
        };
        for (int i = 0; i < inputs.length / 3; i++) {
            String start = inputs[3 * i], end = inputs[3 * i + 1];
            boolean ans = inputs[3 * i + 2].equals ("true");
            System.out.println (Printer.separator ());
            boolean output = tester.canTransform (start, end);
            System.out.printf ("%s and %s -> %s, expected: %b\n", 
                start, end, Printer.wrapColor (output + "", output == ans ? "green" : "red"), ans
            );
        }
    }
}

题目给的tag是一个脑筋急转弯, 不过最后好像很多人不领情, downvote比较高; 我contest的时候自己写的代码:

class Solution {  
    Set<String> set;  

    public boolean canTransform(String start, String end) {  
        set = new HashSet<> ();  
        return dfs (start.toCharArray (), end.toCharArray ());  
    }  

    boolean dfs (char[] chs, char[] che) {  
        String s = new String (chs);  
        if (!set.add (s))  
            return false;  
        if (s.equals (String.valueOf (che)))  
            return true;  
        if (chs.length != che.length)  
            return false;  
        boolean res = false;  
        for (int i = 0; i < chs.length - 1; i++) {  
            if (chs[i] == 'X' && chs[i + 1] == 'L') {  
                swap (chs, i, i + 1);  
                if (dfs (chs, che)) {  
                    res = true;  
                    break;  
                }  
                swap (chs, i, i + 1);  
            } else if (chs[i] == 'R' && chs[i + 1] == 'X') {  
                swap (chs, i, i + 1);  
                if (dfs (chs, che)) {  
                    res = true;  
                    break;  
                }  
                swap (chs, i, i + 1);  
            }  
        }  
        return res;  
    }  

    void swap (char[] chs, int i , int j) {  
        char tmp = chs[i];  
        chs[i] = chs[j];  
        chs[j] = tmp;  
    }  
}

但是TLE了;

其实这个题目还是能感觉到应该是用DP来做的起来的, 但是当我分析root level decision的时候(类似ED的思路, 分析两个string的end之间的关系, 以及怎么利用前面的substring的结果), 发现情况太复杂了; 另外一个当时没有想到怎么用的insight: 这两个move, 一个是把L向左移动, 一个是把R向右移动;

看了一下hint(contest的时候是没有的), 果然, 我上面这个移动的insight是有用的; 只不过我没有发掘到位; 但是我还是要提到一个点, 这个就是面试的时候的交流的重要性了; 我上面这个insight其实已经相当的精确了(我记得当时contest的时候想到这个insight其实没有用掉太多的时间), 如果你一直在和面试官交流, 那么很大程度上面试官看到你走到点子上了, 最后那点就会稍微提示你一下;

Hint 1
Think of the L and R's as people on a horizontal line, where X is a space. The people can't cross each other, and also you can't go from XRX to RXX.

理解了这个应该就很好做了;

写while循环的时候, 很多时候不知道header怎么写, 不慌, 先空着或者直接写true; 后面body里面的逻辑写好了之后再考虑怎么来解决terminate的问题;

另外, hint后面的那个补充, 实际上也不是很trivial, 不知道实际面试的时候怎么想出来;

首先, 这个题目其实设置上面已经给了不少提示了: L只要左边有X, 就可以不停的往左边移动, R只要右边有X, 就可以不停的往右边移动; 我当时做这个题目的时候也尝试过找规律, 但是当时就是被那种类似DP的uncertainty给吓住了; 比如RL, 我认为两者是完全有可能交换位置的; 实际上, 真正有点难度的题目, 你光是想到总结规律还不行, 这些规律往往并不是那么直接; 比如这里, 你就要想到要能排除掉一些不太合理的uncertainty;

理解了上面这两个移动方向的解释, 那么hint的后半段应该也就能理解了, 然后直接加到代码的逻辑里面去;

最后根据hint还是做出来了, 代码写的也不算太丑; 速度是10ms (NA).

感觉这种给你一堆swap之类的operation/move的题目其实也见过很多了, 好几次, 最后的思路其实不是纠结于小的move本身(虽然证明的时候可嫩会用到), 在思考大的算法的时候, 很多时候要从整体来考虑; 比如这题最后实际上就是考虑L和R能walk多少, 而不是被swap了多少次; 马上后面还有一题rising water的题目, 也是给你的是一个一个的step, 但是最后分析的实际上是path;

editorial

Approach #1: Invariant [Accepted]

Intuition

Let's think of 'L' and 'R' as people facing left and right standing on one line, and 'X' as an empty space on that line.

We can ask: what invariants (conditions that remain true after making any move) there are. This is natural for any question that involves transforming some state and asking whether a final state is possible.

我上面的算法虽然看起来比他的算法简单, 但是awice实际上的思考过程非常严谨:

This shows being solid and accessible are necessary conditions. With an induction on the number of people, we can show that they are sufficient conditions. The basic idea of the proof is this: A person on the end either walks away from the others, or walks towards. If they walk away, then let them walk first and it is true; if they walk towards, then let them walk last and it is true (by virtue of the target being solid).

虽然在实际的contest或者面试的过程当中, 往往我们可以直接用必要条件进行判断, 如果能过了直接就过了; 但是也要防止被面试官问到, 为什么你这个就能证明你这个算法是正确的? 一般来说, 用必要条件来证明一个算法的正确性是也有问题的; 这里awice也意识到这个漏洞, 所以进行了一个充分条件的证明;

必要条件->充分条件

不过无论如何, 有一些必要条件总归是比没有东西要好; 如果你觉得好像没有办法拓展你的set of 必要条件了, 那么可以尝试干脆就claim这些就足够了, 就是充分条件; 面试的时候算法题一般不会太折腾人的, 一般只要你前期工作足够, 最后是有可能晃到正确的结论上面的;

class Solution {  
    public boolean canTransform(String start, String end) {  
        if (!start.replace("X", "").equals(end.replace("X", "")))  
            return false;  

        int t = 0;  
        for (int i = 0; i < start.length(); ++i)  
            if (start.charAt(i) == 'L') {  
                while (end.charAt(t) != 'L') t++;  
                if (i < t++) return false;  
            }  

        t = 0;  
        for (int i = 0; i < start.length(); ++i)  
            if (start.charAt(i) == 'R') {  
                while (end.charAt(t) != 'R') t++;  
                if (i > t++) return false;  
            }  

        return true;  
    }  
}

这个实现其实还是不好;

另外, 虽然这里有nested循环, 不要以为就一定是N^2, 这个实际上还是O(N)的算法;

Problem Description

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 <= len(start) = len(end) <= 10000.
Both start and end will only consist of characters in {'L', 'R', 'X'}.

Difficulty:Medium
Total Accepted:914
Total Submissions:4.2K
Contributor:awice
Companies
google
Related Topics
brainteaser

Hint 1
Think of the L and R's as people on a horizontal line, where X is a space. The people can't cross each other, and also you can't go from XRX to RXX.

LC793 SwapAdjacentInLRString

SwapAdjacentInLRString [source code]

header空着

editorial

Approach #1: Invariant [Accepted]

必要条件->充分条件

Problem Description

results matching ""

No results matching ""