思路

使用下面描述的算法可以扰乱字符串 $s1$ 得到字符串 $s2$：

1. 如果字符串的长度为 1 ，算法停止
2. 如果字符串的长度 > 1 ，执行下述步骤：
3. 在一个随机下标处将字符串分割成两个非空的子字符串。即，如果已知字符串 $s$，则可以将其分成两个子字符串 $l(s)$ 和 $r(s)$ ，且满足 $s=l(s)+r(s)$。
4. 随机决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即，在执行这一步骤之后，$s$ 可能是 $s=l(s)+r(s)$ 或者 $s=r(s)+l(s)$ 。
5. 在 $l(s)$ 和 $r(s)$ 这两个子字符串上继续从步骤 1 开始递归执行此算法。

给定两个相同长度的字符串 $s1$、$s2$，要求判断 $s2$ 是否是 $s1$ 的 scramble string

完全不会做啊，在看了题解后，有：

1. Scrambled 是一种等价关系，$s1$ 是 $s2$ 的 scrambled string，反之亦然。如果两个字符串相等，那它们互为 scramble string。

2. 如果两个字符串所含各字符的个数不同，那一定不是 scrambled string。

3. 存在一个正整数 $0 < i < s1.length$，记字符串长度为 $len$，$s1=s1[0, i]+s1[i, len]$，$s2=s2[0, i]+s2[i, len]$，如果 $s1$ 是 $s2$ 的 scrambled string，那就会存在一种变换，

   3.1. 没有交换子串时，使得 $s1[0, i]$ 和 $s2[0, i]$ 互为 scrambled string，$s1[i, len]$ 和 $s2[i, len]$ 互为 scrambled string。

   3.2. 或者，交换了子串时，$s1[0, i]$ 和 $s2[len - i, len]$ 互为 scrambled string，$s1[i, len]$ 和 $s2[0, len - i]$ 互为 scrambled string。

记两个字符串是否为 scrambled string 为$f(s1,s2)$，有状态转移方程：

$$f(s1,s2)=\left\{ \begin{aligned} true, s1=s2\\ false, s1, s2 所含各字符个数不等\\ ⋁^{len - 1}_{i=1} \left( \begin{aligned} f(s1[0, i], s2[0, i])\wedge f(s1[i, len], s2[i, len])\vee \\ f(s1[0, i], s2[len - i, len])\wedge f(s1[i, len], s2[0, len - i]) \end{aligned} \right),else \end{aligned} \right.\\$$

记忆化搜索

此外，为了避免过多使用字符串分割合并截取的操作，入参可以改为字符串起始下标和长度的形式来提高性能。

这里采用递归的形式来写这个题目，加上缓存进行记忆化搜索，时间复杂度 $O(n^4)$，空间复杂度 $O(n^3)$。

ts
function isScramble(s1: string, s2: string): boolean {
    const sL = s1.length
    const cache = new Array(sL).fill(0).map(() => new Array(sL).fill(0).map(() => new Array(sL)))
    const dfs = (l1: number, l2: number, len: number) => {
        if (cache[l1][l2][len] !== undefined) {
            return cache[l1][l2][len]
        }
        if (s1.slice(l1, l1 + len) === s2.slice(l2, l2 + len)) {
            return cache[l1][l2][len] = true
        }
        const charMap = new Map<string, number>()
        for (let i = 0; i < len; i++) {
            charMap.set(s1[l1 + i], (charMap.get(s1[l1 + i]) || 0) + 1)
            charMap.set(s2[l2 + i], (charMap.get(s2[l2 + i]) || 0) - 1)
        }
        let flag = true
        for (let i of charMap.values()) {
            flag &&= i === 0
        }
        if (!flag) {
            return cache[l1][l2][len] = false
        }
        if (len === 1) {
            return cache[l1][l2][len] = true
        }
        let ans = false
        for (let i = 1; i < len; i++) {
            ans ||= (dfs(l1, l2, i) && dfs(l1 + i, l2 + i, len - i)) ||
                (dfs(l1, l2 + len - i, i) && dfs(l1 + i, l2, len - i))
        }
        return cache[l1][l2][len] = ans
    }
    return dfs(0, 0, sL)
};

发现一个小问题，上面涉及字符串的操作其实可以直接去掉的，测了一下，它减少迭代步数省下的运行时间，比操作字符串所花时间还少。

ts
function isScramble(s1: string, s2: string): boolean {
    const sL = s1.length
    const cache = new Array(sL).fill(0).map(() => new Array(sL).fill(0).map(() => new Array(sL)))
    const dfs = (l1: number, l2: number, len: number) => {
        if (cache[l1][l2][len] !== undefined) {
            return cache[l1][l2][len]
        }
        if (len === 1) {
            return cache[l1][l2][len] = s1[l1] === s2[l2]
        }
        let ans = false
        for (let i = 1; i < len; i++) {
            ans ||= (dfs(l1, l2, i) && dfs(l1 + i, l2 + i, len - i)) ||
                (dfs(l1, l2 + len - i, i) && dfs(l1 + i, l2, len - i))
        }
        return cache[l1][l2][len] = ans
    }
    return dfs(0, 0, sL)
};

递推式

很显然，我们可以改用递推式的写法，这里先循环子串长度，避免后面迭代时值还没有。

ts
function isScramble(s1: string, s2: string): boolean {
    const sL = s1.length
    const dp = new Array(sL + 1).fill(0).map(() => new Array(sL).fill(0).map(() => new Array(sL)))
    for (let k = 1; k <= sL; k++) {
        for (let i = 0; i + k <= sL; i++) {
            for (let j = 0; j + k <= sL; j++) {
                if (k === 1) {
                    dp[k][i][j] = s1[i] === s2[j]
                } else {
                    let ans = false
                    for (let l = 1; l < k; l++) {
                        ans ||= (dp[l][i][j] && dp[k - l][i + l][j + l]) ||
                            (dp[l][i][j + k - l] && dp[k - l][i + l][j])
                    }
                    dp[k][i][j] = ans
                }
            }
        }
    }
    return dp[sL][0][0]
};