Scramble String

这道题应该是最复杂的一道DP了，首先题意上的左右旋转就很难理解，其次因为维度太高一般难以想到，这里思路直接放九章的截图了

下面是代码

public class Solution {
    public boolean isScramble(String s1, String s2) {
        char[] a = s1.toCharArray();
        char[] b = s2.toCharArray();

        if (a.length != b.length) {
            return true;
        }

        int n = a.length;

        boolean[][][] dp = new boolean[n][n][n + 1];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j][1] = (a[i] == b[j]);
            }
        }

        for (int k = 2; k < n + 1; k++) {
            for (int i = 0; i < n - k + 1; i++) {
                for (int j = 0; j < n - k + 1; j++) {
                    dp[i][j][k] = false;
                    for (int w = 1; w < k; w++) {
                        if (dp[i][j][w] && dp[i + w][j + w][k - w]) {
                            dp[i][j][k] = true;
                            break;
                        }

                        if (dp[i][j + k - w][w] && dp[i + w][j][k - w]) {
                            dp[i][j][k] = true;
                            break;
                        }
                    }
                }
            }
        }

        return dp[0][0][n];
    }
}