写在前面

今天刷了这道DP问题，想了半天，没有思路，结果看了题解大吃一惊，这道问题居然要O(n^4)的时间复杂度，天真的我一直以为LeetCode题最多也就3次方呢。。。前两天跪了的美团一面也遇到了类似的问题，自己对复杂度估计很有问题。。。当时是求一个数组前k个最小的的数组成的数组，简单排序就可以了，然后面试官让我优化，我想了半天都一直在往O(n)奔，结果面试官提示说优化快排的过程，在快排的过程中就可以完成题目的求解，题目在这儿：最小的k个数，唉，之前还以为自己还凑活，越刷题发现自己越菜，甚至很多以前想到过的思路都想不起来了，真是太难受了。。。

---

题目

核心思路

穷举

其实根据我做的不多的题来感觉，这类问题最重要的还是先考虑清楚怎么通过枚举所有状态来解决问题，有了这步之后再去优化，就会稍微简单一些。根据题目的意思，扰乱字符串就相当于是把字符串分成左子串和右子串，对应于树的左子树和右子树。那么，一个字符串str1可以转化为他的扰乱字符串str2也就意味着要么str1的左子串和str2的左子串相等(符合扰乱规则)，同时右子串也相等(符合扰乱规则)；要么str1的左子串和str2的右子串相等并且剩余部分也相等(符合扰乱规则)，而题目中只是说递归的分割为两个非空子串，并没有提如何去分割，也就是说我们需要遍历每一种分割方法，然后分别进行上述考虑以此来穷举所有可能。因为题目就是递归分割的字符串，而这道题又可以看作是树形结构，所以可以把重复的步骤交给递归。假设分割点为i的话可以得到如下的递推公式：

//s1的左子串等于s2的左子串且右子串相等
boolean flag1 = (isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i)));
//s1的左子串等于s2的右子串且剩余部分相等
boolean flag2 = (isScramble(s1.substring(0, i), s2.substring(s2.length() - i)) && isScramble(s1.substring(i), s2.substring(0, s2.length() - i)));

这道题的下标计算真的比较愁人，多拿两个例子试一试或许能比较好的找到下标的关系。

图示

同色表示子串相等(可以通过扰乱转化)

穷举代码

class Solution {
    public boolean isScramble(String s1, String s2) {
        if(s1 == null || s2 == null)
            return false;
        if(s1.length() == 1){
            return s1.charAt(0) == s2.charAt(0);
        }
        if(s1.length() == 2){
            return (s1.charAt(0) == s2.charAt(0) && s1.charAt(1) == s2.charAt(1)) || (s1.charAt(1) == s2.charAt(0) && s1.charAt(0) == s2.charAt(1));
        }
        boolean ans = false;
        for(int i = 1; i < s1.length() && !ans; i++){
            ans = ans || (isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i))) || (isScramble(s1.substring(0, i), s2.substring(s2.length() - i)) && isScramble(s1.substring(i), s2.substring(0, s2.length() - i)));
        }
        return ans;
    }
}

有了递归的递推公式，代码就比较简单了，对于长度等于2的判断其实可加可不加，不加也可以在递归里遍历到，加了能稍微减少一点压栈弹栈。

穷举优化

(1)备忘录优化

递归穷举时间复杂度很高，优化是必须的，而递归的优化就不得不想到备忘录了，所以我们可以使用一个备忘录数组来记录之前计算过的结果。不过还需要考虑备忘录用几维，表示什么，由于考虑的问题在递归时与字符串的子串相关，那么至少需要一个起始点和一个结束点，又因为需要同时记录s1和s2两个字符串的子串，也就是说需要四维数组来记录访问过的值，还是很恐怖的。。。

备忘录优化代码

根据上边的穷举法把取子串的操作变成每次递归传递下标然后每访问过一对串就添加进备忘录即可。

class Solution {
    String s1;
    String s2;

    public boolean isScramble(String s1, String s2) {
        if (s1 == null || s2 == null || s1.length() != s2.length())
            return false;
        this.s1 = s1;
        this.s2 = s2;
        int len = s1.length();
        int[][][][] memo = new int[len][len][len][len];
        return matches(0, len - 1, 0, len - 1, memo);
    }

    public boolean matches(int i, int j, int m, int n, int[][][][] memo) {
        if (memo[i][j][m][n] != 0) {
            return memo[i][j][m][n] == 1;// 0为未访问，1为可以匹配，2为不匹配
        }
        if (j - i == 0) {
            memo[i][j][m][n] = s1.charAt(i) == s2.charAt(m) ? 1 : 2;
            return memo[i][j][m][n] == 1;
        }
        if (j - i == 1) {
            boolean temp = (s1.charAt(i) == s2.charAt(m) && s1.charAt(j) == s2.charAt(n))
                    || (s1.charAt(j) == s2.charAt(m) && s1.charAt(i) == s2.charAt(n));
            memo[i][j][m][n] = temp ? 1 : 2;
            return memo[i][j][m][n] == 1;
        }

        boolean ans = false;
        for (int len = 1; len < j - i + 1 && !ans; len++) {
            ans = ans || (matches(i, i + len - 1, m, m + len - 1, memo) && matches(i + len, j, m + len, n, memo))
                    || (matches(i, i + len - 1, n - len + 1, n, memo) && matches(i + len, j, m, n - len, memo));
        }
        memo[i][j][m][n] = ans ? 1 : 2;
        return ans;
    }
}

(2)根据字母出现次数优化

说实话这个优化我是没想到，被官方的示例给带跑了，我以为它提供的测试用例怎么也得是满足字母出现次数相同的情况下才判断是不是扰乱吧。。。实际可能确实是这样，但是对于递归考虑子串的时候，还是很有可能会出现字母出现次数都不同的情况，所以每层递归都优先判断两个子串的字母出现次数是否相同，不同的话就不需要继续深层递归了。

优化代码

class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1 == null || s2 == null)
            return false;
        if (s1.equals(s2))
            return true;
        if (s1.length() == 1) {
            return s1.charAt(0) == s2.charAt(0);
        }
        int[] letters = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            letters[s1.charAt(i) - 'a']++;
            letters[s2.charAt(i) - 'a']--;
        }

        for (int i = 0; i < 26; i++) {
            if (letters[i] != 0)
                return false;
        }

        boolean ans = false;
        for (int i = 1; i < s1.length() && !ans; i++) {
            ans = ans
                    || (isScramble(s1.substring(0, i), s2.substring(0, i))
                            && isScramble(s1.substring(i), s2.substring(i)))
                    || (isScramble(s1.substring(0, i), s2.substring(s2.length() - i))
                            && isScramble(s1.substring(i), s2.substring(0, s2.length() - i)));
        }
        return ans;
    }
}

这样优化后运行时间可以达到2ms，极大的进行了剪枝，保证了不满足条件的尽快被筛选掉。

动态规划

或许直到现在我才真的直到什么是动态规划，为什么动态规划效率高，以前一直模糊的不得了。
递归是自顶向下的，它会先考虑两个完整的字符串，然后不断深入，直到递归出口，也就是子串只剩下一个字符时，开始向上返回结果，最终得到最后的结果；而动态规划实际上省略了深入的过程，自底向上其实就是直接考虑递归出口所要解决的问题，也就是一个字符时的情况，这也是为什么DP问题总要去考虑最小子问题的原因，然后根据最小子问题向上一点点得到最终的最优解。
另外，DP的作用是提高效率，他是通过自底向上复用先前的结果以此达到天然剪枝的效果，不过实际上他还是会遍历所有的可能，这也是为什么上边的剪枝结果要比DP更快，上边的剪枝在字符串还是比较长的时候就有可能直接剪掉返回，而DP则不会，DP还是要从短到长一点点遍历每个可能。

DP思路

最小子问题：通过上边的思考，两个字符串的最小子问题就是只有一个字符的情况，在这种情况下，是不是满足扰乱的条件就是看这两个字符是不是相等即可。
DP数组的定义：通过穷举加备忘录时的考虑，我们可以定义一个四维数组dp[i][j][m][n]来表示s1 i 到 j 的子串和s2 m 到 n 的子串是否匹配，不过一方面满足扰乱的前提是两个字符串长度相等，所以j - i == n - m的部分才是须要考虑的；另一方面，我们使用DP自底向上是要从最小子问题凑出最终结果，所以这样枚举的时候不方便，换成长度更合适，字符串的DP问题很多都是通过枚举长度来解决的。dp[len][i][j]表示s1从 i 开始长度是len的子串与s2从 j 开始长度是len的子串是否满足扰乱关系。
状态转移方程：对于长度大于等于2的两个子串，通过递归时的图示很容易可以想到类似递归的转移方程：对于每个确定的分割方式，要么s1左子串与s2左子串相等(可以通过扰乱转化)，同时另一部分相等(可以通过扰乱转化)；要么s1左子串与s2右子串相等，同时剩余部分相等。

boolean temp = false;
for (int k = 1; k < len && !temp; k++) {
    temp = temp || dp[k][i][j] && dp[len - k][i + k][j + k]
          || dp[k][i][j + len - k] && dp[len - k][i + k][j];
}
dp[len][i][j] = temp;

上边的代码通过遍历每一个可能的分割点k，然后对每个分割点分别获取dp[k][i][j] && dp[len - k][i + k][j + k]表示上述第一种情况；dp[k][i][j + len - k] && dp[len - k][i + k][j]表示上述第二种情况。这里的下标真的不是很好算，挺愁人的。最后，根据dp数组的定义，题目求解的答案即是dp[s1.length][0][0]。

DP代码

class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1 == null || s2 == null || s1.length() != s2.length())
            return false;
        int length = s1.length();
        boolean[][][] dp = new boolean[length + 1][length][length]; // dp[len][i][j] 表示从i,j开始，长度为len的字符串是否匹配

        for (int len = 1; len <= length; len++) {
            for (int i = 0; i < length - len + 1; i++) {
                for (int j = 0; j < length - len + 1; j++) {
                    if (len == 1) {
                        dp[len][i][j] = s1.charAt(i) == s2.charAt(j);
                    } else {
                        boolean temp = false;
                        for (int k = 1; k < len && !temp; k++) {
                            temp = temp || dp[k][i][j] && dp[len - k][i + k][j + k]
                                    || dp[k][i][j + len - k] && dp[len - k][i + k][j];
                        }
                        dp[len][i][j] = temp;
                    }
                }
            }
        }

        return dp[length][0][0];
    }
}

总结

DP问题真的是一类很难的问题，记得前些天看的ycx讲的DP问题提到，这类问题在定义dp数组的时候更多时候是需要靠经验的，而且定义的选择稍有不对就很可能解决不了问题，还是需要慢慢去积累，真的好难。最后，如果想看闫氏DP分析法，请点击这里，讲解的还是很透彻的，不过DP难是肯定了，需要继续努力，进步啊，感恩相遇~