算法1

(一个非常慢的动态规划做法) $O(n^4)$

dp[k][i][j] 表示s1从i开始, s2从j开始的长度为k的字符串是否okay.

C++ 代码

class Solution {
public:
    bool isScramble(string s1, string s2) {
        int len = s1.length();
        if (len == 0 || len != s2.length()) return false;
        vector<vector<vector<bool>>> dp(len + 10, vector<vector<bool>>(len + 10, vector<bool>(len + 10, false)));
        //dp[k][i][j] = dp[m][i][j] && dp[k - m][i + m][j + m] || dp[m][i][j + k - m] && dp[k - m][i + m][j];
        for (int i = 0;i < len;i ++) {
            for (int j = 0;j < len;j ++) {
                dp[1][i][j] = s1[i] == s2[j];
            }
        }
        for (int k = 2;k <= len;k ++) {
            for (int i = 0;i < len;i ++) {
                for (int j = 0;j < len;j ++) {
                    for (int m = 1;m < k;m ++) {
                        if (i + m <= len - 1 && j + m <= len - 1 && k - m >= 0) 
                        dp[k][i][j] = dp[k][i][j] | dp[m][i][j] & dp[k - m][i + m][j + m];
                        if (j + k - m >= 0 && j + k - m <= len - 1 && i + m <= len - 1 && k - m >= 0)
                        dp[k][i][j] = dp[k][i][j] | dp[m][i][j + k - m] & dp[k - m][i + m][j];
                    }
                }
            }
        }
        return dp[len][0][0];
    }
};