算法

(DP) $O(n^3)$

题目的样例是从中间开始分割做树，但其实是可以从任意点开始切割作为树的根节点，其他非叶子的子节点也是一样可以从任意点切割。我们可以考虑用dp来判断 s2 是否为 s1 的干扰字符串.

• 我们用一个数组dp[n][i][j]表示s1[i..i+n-1]和s2[j..j+n-1]两个子串是否是scramble的
• 初始条件：当长度为1时，如果字符串相等就符合，否则不符合。
• 当长度为n时，将字符串表示的树的根节点放在第2至n-1元素上。某一边的子树为空是无意义的，因为就是自身。也就是长度为n的字符串有n-1种情况，分别是1,k。k的取值范围是1到n-1。这n-1中情况，只要有一种符合，就说明这个长度为n的字符串符合。
• 每一种情况，又有两种方式，s1的前k个和s2的前k个比较，s1后n-k个和s2的后n-k比较。也可以是s1的前k个和s2的后k个比较。两种方式对应的就是这个子树不交换和交换的场景。
• 我们只要计算计算长度为n的, s1[i, i+n-1]和s2[j, j+n-1]是否是scramble的，通过遍历所有子串划分是否存在有一个满足即可
• 转移方程式：dp[n][i][j] = dp[k][i][j] && dp[n-k][i+k][j+k] || dp[k][i][j+n-k] && dp[n-k][i+k][j] （这里k是s1部分的左子串的长度）
• 最后通过 dp[n][0][0] 来判断整个字符串是否是干扰字符串

C++ 代码

class Solution {
public:
    bool isScramble(string s1, string s2) {
        int size = s1.length();
        if (size != s2.length()) { 
            return false; 
        }
        // 非字符集合相等的提前剪枝
        string sort_s1 = s1; 
        sort(sort_s1.begin(), sort_s1.end());
        string sort_s2 = s2; 
        sort(sort_s2.begin(), sort_s2.end());
        if (sort_s1 != sort_s2) { 
            return false; 
        }
        // dp[n][i][j]表示s1[i..i+n-1]和s2[j..j+n-1]两个子串是否是scramble的
        // 迭代起点，对长度为1的直接比较计算出结果; 其他的初始化为false
        bool dp[size+1][size][size];
        for (int i = 0; i < size+1; i++) {
            for (int j = 0; j < size; j++) {
                for (int k = 0; k < size; k++) {
                    if (i == 0 || i == 1 && s1[j] == s2[k]) {
                        dp[i][j][k] = true;
                    } 
                    else {
                        dp[i][j][k] = false;
                    }
                }
            }
        }
        // 依次计算长度更大的, 对于长度为n的情况，直接看所有的子串划分情况是否有一个满足的
        // 由于n是递增的，因此子串的都是已经计算过的
        for (int n = 2; n < size + 1; n++) {
            for (int i = 0; i <= size - n; i++) {
                for (int j = 0; j <= size - n; j++) {
                    // 计算长度为n的, s1[i, i+n-1]和s2[j, j+n-1]是否是scramble的
                    // 通过遍历所有子串划分是否存在有一个满足即可
                    for (int k = 1; k < n; k++) { // k是s1部分的左子串的长度
                        if (dp[k][i][j] && dp[n-k][i+k][j+k] || dp[k][i][j+n-k] && dp[n-k][i+k][j]) {
                            dp[n][i][j] = true;
                            break;
                        }
                    }
                }
            }
        }
        // 最后结果就是s1[0,size]和s2[0,size]是否匹配
        return dp[size][0][0];
    }
};