LeetCode: Scramble String

LeetCode: Scramble String 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

/**
 * Description: TODO: cannot understand
 * <p/>
 * http://www.lifeincode.net/programming/leetcode-scramble-string-java/
 *
 * @author hzhou
 */
public class ScrambleString {
    public boolean isScramble(String s1, String s2) {
        //Check lengths.
        if (s1.length() != s2.length()) {
            return false;
        }
        if (s1.equals(s2)) {
            return true;
        }
        int L = s1.length();
        boolean[][][] scramble = new boolean[L][L][L];
        for (int i = 0; i < L; i++) {
            for (int j = 0; j < L; j++) {
                if (s1.charAt(i) == s2.charAt(j)) {
                    scramble[0][i][j] = true;
                }
            }
        }
        for (int k = 2; k <= L; k++) {
            for (int i = L - k; i >= 0; i--) {
                for (int j = L - k; j >= 0; j--) {
                    boolean canScramble = false;
                    for (int m = 1; m < k; m++) {
                        canScramble = (scramble[m - 1][i][j] && scramble[k - m - 1][i + m][j + m]) || (
                                scramble[m - 1][i][j + k - m] && scramble[k - m - 1][i + m][j]);
                        if (canScramble) {
                            break;
                        }
                    }
                    scramble[k - 1][i][j] = canScramble;
                }
            }
        }
        return scramble[L - 1][0][0];
    }
}