[leetcode]Scramble String

三维DP，用备忘录方式写很简单。但是正如那天讨论时说的那样，使用备忘录法，可能会对复杂度和递推公式理解不够深刻。

这道题目的递推公式很简单，但是复杂度的话。。。因为数组里的值每个都被计算仅为一次，所以应该是O(n^3)

要注意的是，最后一维的是len+1

public class Solution {
    public boolean isScramble(String s1, String s2) {
        char[] ca1 = s1.toCharArray();
        char[] ca2 = s2.toCharArray();
        if (s1.length() != s2.length()) return false;
        int len = s1.length();
        if (len == 0) return true;
        int[][][] mx = new int[len][len][len+1];
        for (int i = 0; i < len; i++)
            for (int j = 0; j < len; j++)
                for (int k = 0; k < len+1; k++)
                    mx[i][j][k] = -1; // not visited;
        return isScramble(ca1, ca2, 0, 0, len, mx);
    }
    
    public boolean isScramble(char[] ca1, char[] ca2, int i1, int i2, int len, int[][][] mx)
    {
        if (len == 1) return ca1[i1] == ca2[i2];
        if (mx[i1][i2][len] != -1)
        {
            return mx[i1][i2][len] == 1;
        }
        for (int k = 1; k < len; k++)
        {
            if (isScramble(ca1, ca2, i1, i2, k, mx) && isScramble(ca1, ca2, i1+k, i2+k, len-k, mx))
            {
                mx[i1][i2][len] = 1;
                return true;
            }
            if (isScramble(ca1, ca2, i1, i2+len-k, k, mx) && isScramble(ca1, ca2, i1+k, i2, len-k, mx))
            {
                mx[i1][i2][len] = 1;
                return true;
            }
        }
        mx[i1][i2][len] = 0;
        return false;
    }
}