算法一：区间DP

具体请查看注释！

参考代码：

class Solution {
public:
    /*  
        状态表示：f[i][j][k]：表示a串[i, i + k - 1]和b串[j, j + k - 1]是否匹配！
            k：表示区间长度
        状态计算：考虑分割点，将f[i][j][k]划分为k - 1类，用u表示分割点（左长度为u，右长度为k - u）
            1. 对应相等：f[i][j][u] && f[i + u][j + u][k - u]
            2. 交叉相等：f[i][j + k - u][u] && f[i + u][j][k - u]
            即：f[i][j][u] = f[i][j][u] && f[i + u][j + u][k - u] || f[i][j + k - u][u] && f[i + u][j][k - u]
        最终答案：f[0][0][n]

        时间复杂度：O(n^4)
    */

    bool isScramble(string a, string b) {
        int n = a.size();
        vector<vector<vector<bool>>> f(n, vector<vector<bool>>(n, vector<bool>(n + 1)));

        for(int k = 1; k <= n; k ++) // 区间长度
            for(int i = 0; i + k - 1 < n; i ++) // a串左端点
                for(int j = 0; j + k - 1 < n; j ++) // b串左端点
                    if(k == 1){ // 区间长度为1，直接判断即可
                        if(a[i] == b[j]) f[i][j][k] = true;
                    }else{
                        // 枚举分割点到左端点长度（划分成k - 1类）
                        for(int u = 1; u < k; u ++)
                            if(f[i][j][u] && f[i + u][j + u][k - u] || f[i][j + k - u][u] && f[i + u][j][k - u]){
                                f[i][j][k] = true;
                                break;
                            }
                    }

        return f[0][0][n];
    }
};

算法二：递归（目前已经TLE）

参考代码：

class Solution {
public:
    bool isScramble(string a, string b) {
        if(a == b) return true;
        string aa = a, bb = b;
        sort(aa.begin(), aa.end()), sort(bb.begin(), bb.end());
        // 不一样则一定无法匹配
        if(aa != bb) return false;

        // 枚举分割点到左端点长度
        int n = a.size();
        for(int i = 1; i < n; i ++){
            // 处理对应情况：
            if(isScramble(a.substr(0, i), b.substr(0, i)) && isScramble(a.substr(i), b.substr(i)))
                return true;
            // 处理交叉情况：
            if(isScramble(a.substr(0, i), b.substr(n - i)) && isScramble(a.substr(i), b.substr(0, n - i)))
                return true;
        }
        return false;
    }
};