Scramble String

题目
Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

答案

class Solution {
    public boolean isScramble(String ss1, String ss2) {
        int n = ss1.length();
        if(ss2.length() != n) return false;
        char[] s1 = ss1.toCharArray(), s2 = ss2.toCharArray();
        boolean[][][] f = new boolean[n][n][n + 1];

        // len = 1
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++)
                f[i][j][1] = (s1[i] == s2[j]);
        }

        for(int len = 2; len <= n; len++) {
            for(int i = 0; i <= n - len; i++) {
                for(int j = 0; j <= n - len; j++) {
                    f[i][j][len] = false;

                    // S = S1 S2
                    // T = T1 T2

                    // If S1 可以变成T1, S2可以变成T2, we are happy :)
                    // If S1 可以变成T2, S2可以变成T1, we are also happy :)

                    for(int w = 1; w <= len - 1; w++) {

                        if(f[i][j][w] && f[i + w][j + w][len - w])
                            f[i][j][len] = true;

                        if(f[i][j + len - w][w] && f[i + w][j][len - w])
                            f[i][j][len] = true;
                    }
                }
            }
        }
        return f[0][0][n];
    }
}