代码1

f[i][j][k] 表示 s1的 i 到 i + k 子字符是不是与 s2 的 j 到 j + k 的子字符符合。
Runtime: Runtime: 6 ms, faster than 39.75% of Java online submissions for Scramble String.

class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        int len = s1.length();
        boolean[][][] f = new boolean[len][len][len + 1];
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (s1.charAt(i) == s2.charAt(j)) f[i][j][1] = true;
            }
        }
        for (int k = 2; k <= len; k++) {
            for (int i = 0; i + k <= len; i++) {
                for (int j = 0; j + k <= len; j++) {
                    for (int q = 1; q < k; q++) {
                        if (f[i][j][q] && f[i + q][j + q][k - q]) {
                            f[i][j][k] = true;
                            break;
                        }
                        if (f[i][j + k - q][q] && f[i + q][j][k - q]) {
                            f[i][j][k] = true;
                            break; 
                        }
                    }
                }
            }
        }
        return f[0][0][len];
    }
}