LeetCode 87. 扰乱字符串

2026-05-30 HGNULB 约 12 分钟

文章信息 6 个分类 2 个标签

分类

题目描述

✅ 87. 扰乱字符串

题意分析

题目定义了一种对字符串的操作：如果字符串长度大于 1，就在任意位置把它切成非空的两段，然后可以选择保持两段的先后顺序，也可以选择把两段交换，接着对每一段递归地重复这个过程。给定 s1 和 s2，问 s2 能不能由 s1 经过若干次这样的操作得到。

读题时最容易漏掉的是「递归」二字：切分不是只做一次，而是在每一层都可以继续切、继续选择是否交换。所以这不是一个平铺的重排问题，而是一棵二叉切分树的形状与左右翻转的组合。

另一个必须抓住的信号是「切成非空的两段」。这保证了每次切分后两段长度都至少为 1，子问题严格变小，递归一定会终止；同时也意味着枚举切点时下标必须落在 $1$ 到 $len-1$ 之间，取到 $0$ 或 $len$ 会造出长度为 0 的子问题而死循环。

还有一个隐含的强约束：整个操作过程只重排字符，从不增删也不替换。因此两个字符串必须等长，而且任意一对互为扰乱串的子串，其字符出现次数必然完全一致。反过来不成立——字符多重集合相同只是必要条件，官方给的 s1 = "abcde"、s2 = "caebd" 就是计数相同但答案为 false 的例子。

规模上字符串长度不超过 30，字符集是小写字母。这个上限给得很低，暗示允许一个状态数在 $n^3$ 量级、单个状态还要付出线性代价的解法。

边界处理有三处：长度不等直接判否；两段完全相同时直接判是（这同时也是长度为 1 的基例）；字符计数不同时可以立刻剪掉整棵子树。

解法：记忆化搜索（递归划分 + 剪枝）

核心思路

先按定义写暴力。要判断 s1 能否变成 s2，就枚举第一刀切在哪里：设切点把 s1 分成长度 $k$ 的左半和长度 $len-k$ 的右半。如果这一层不交换，那么 s1 的左半要能变成 s2 的左半（同样长 $k$），s1 的右半要能变成 s2 的右半；如果这一层交换，那么 s1 的左半要对应 s2 的末尾 $k$ 个字符，s1 的右半要对应 s2 的开头 $len-k$ 个字符。两种方式任意一种成立即可，两个子问题之间是「与」的关系。

这个暴力的分支因子是 $2(len-1)$，深度是 $O(\log len)$ 到 $O(len)$，不加处理会指数爆炸。瓶颈在哪？在于同一个子问题会被不同的切分路径反复问到——比如 s1 的某一段和 s2 的某一段配对，可能从若干条不同的切分序列走到。

观察到一件关键的事：一个子问题被完整确定，只需要三个量——s1 里那一段的起点 i1、s2 里那一段的起点 i2、以及它们共同的长度 len。之所以只用记一个长度而不是两个区间，是因为互相比较的两段必然等长，这由「只重排不增删」保证。于是状态空间被压到了 $O(n^3)$。

状态定义写清楚：$f(i_1, i_2, len)$ 表示 s1 从下标 $i_1$ 开始、长度为 $len$ 的子串，能否通过题目定义的操作变成 s2 从下标 $i_2$ 开始、长度为 $len$ 的子串。转移就是对切点 $k$ 从 $1$ 到 $len-1$ 取析取：不交换那一支要求 $f(i_1, i_2, k)$ 与 $f(i_1+k, i_2+k, len-k)$ 同时成立，交换那一支要求 $f(i_1, i_2+len-k, k)$ 与 $f(i_1+k, i_2, len-k)$ 同时成立。

两支的区别全在 s2 的起点上：交换后 s1 的前 $k$ 个字符要去对齐 s2 那一段的末尾 $k$ 个字符，起点因此是 $i_2 + len - k$；而 s1 剩下的 $len-k$ 个字符去对齐 s2 的开头，起点仍是 $i_2$。

基例有两条。其一，两段字符完全相同时直接为真，这条同时覆盖了 $len = 1$ 的情形——没有它，$len=1$ 的状态会进入一个空的 $k$ 循环并错误地返回假。其二，两段的 26 个字母计数向量不相等时直接为假，这是剪枝而非正确性所必需，但它把绝大多数无望的分支砍在了根上，是这道题能跑进时限的关键。

解题步骤

先比长度，不等直接返回假。为什么放在最前面：后续所有下标推演都建立在等长假设上，不先挡住会越界。

开一个三维记忆化表，第三维长度要开到 $n+1$，因为 len 的取值范围是 $1$ 到 $n$。为什么用可空的 Boolean 而不是 boolean：需要区分「还没算过」和「算过且结果为假」，用原始类型的默认值 false 会把两者混为一谈。Go 版做不到可空，所以额外开了一张 seen 表来标记「已计算」。

进入递归后先查记忆化表，命中就直接返回。为什么第一件事就查表：这是把指数级压回多项式的唯一手段，任何在查表之前做的重活都会被重复付出。

判断两段是否逐字符相同，是则记为真并返回。为什么这是基例：长度为 1 时 $k$ 的循环不会执行，必须靠这一条给出正确答案；长度大于 1 时它也是一个合法的提前返回，因为「一次都不切」本身就是允许的。

统计两段的字母计数差，任意一位不为零就记为假并返回。为什么这一步值得付出 $O(len)$：它把「字符集都对不上」的子树整棵砍掉，实测能让运行时间下降一个数量级。

枚举切点 $k$ 从 $1$ 到 $len-1$，先试不交换的一对子问题，再试交换的一对，任一对同时为真就记为真并返回。为什么 $k$ 不能取 $0$ 或 $len$：那会产生长度为 0 的空段，子问题不比原问题小，递归不收敛。

全部切点都失败后记为假并返回。为什么假结果也必须写进记忆化表：否则失败的状态每次都要重算一遍完整的切点循环，剪枝的收益会被全部吃掉。

以 s1 = "great"、s2 = "rgeat" 走一遍：调用 $f(0,0,5)$。两段 "great" 与 "rgeat" 不相同，字母计数都是 ${a,e,g,r,t}$ 各一个，通过剪枝。切点 $k=1$：不交换需要 $f(0,0,1)$，即 'g' 对 'r'，假；交换需要 $f(0, 0+5-1, 1)$，即 'g' 对 s2[4]='t'，也假。切点 $k=2$：不交换先算 $f(0,0,2)$，即 "gr" 对 "rg"——两段不同但计数相同，其内部再枚举切点，只有 $k=1$ 可取，不交换分支是 'g' 对 'r' 为假，交换分支需要 $f(0, 0+2-1, 1)$ 即 'g' 对 s2[1]='g' 为真，且 $f(0+1, 0, 2-1)$ 即 s1[1]='r' 对 s2[0]='r' 为真，两者同真，所以 $f(0,0,2)$ 为真。回到上层，还需要 $f(0+2, 0+2, 5-2) = f(2,2,3)$，即 "eat" 对 "eat"，逐字符相同，命中第一条基例为真。两个子问题都为真，$f(0,0,5)$ 记为真并返回。最终答案是 true。

代码实现

// 核心实现：记忆化搜索（递归划分 + 剪枝），维护必要状态并避免重复处理。
class Solution {
    private String s1;
    private String s2;
    private Boolean[][][] memo;

    public boolean isScramble(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        this.s1 = s1;
        this.s2 = s2;
        int n = s1.length();
        memo = new Boolean[n][n][n + 1];
        return dfs(0, 0, n);
    }

    private boolean dfs(int i1, int i2, int len) {
        if (memo[i1][i2][len] != null) {
            return memo[i1][i2][len];
        }

        if (s1.regionMatches(i1, s2, i2, len)) {
            memo[i1][i2][len] = true;
            return true;
        }
        if (!sameCount(i1, i2, len)) {
            memo[i1][i2][len] = false;
            return false;
        }

        for (int k = 1; k < len; k++) {
            if (dfs(i1, i2, k) && dfs(i1 + k, i2 + k, len - k)) {
                memo[i1][i2][len] = true;
                return true;
            }
            if (dfs(i1, i2 + len - k, k) && dfs(i1 + k, i2, len - k)) {
                memo[i1][i2][len] = true;
                return true;
            }
        }

        memo[i1][i2][len] = false;
        return false;
    }

    private boolean sameCount(int i1, int i2, int len) {
        int[] cnt = new int[26];
        for (int k = 0; k < len; k++) {
            cnt[s1.charAt(i1 + k) - 'a']++;
            cnt[s2.charAt(i2 + k) - 'a']--;
        }
        for (int x : cnt) {
            if (x != 0) {
                return false;
            }
        }
        return true;
    }
}

// 核心实现：记忆化搜索（递归划分 + 剪枝），维护必要状态并避免重复处理。
func isScramble(s1 string, s2 string) bool {
    if len(s1) != len(s2) {
        return false
    }
    n := len(s1)

    memo := make(map[[3]int]bool)
    seen := make(map[[3]int]bool)

    var sameCount func(i1, i2, length int) bool
    sameCount = func(i1, i2, length int) bool {
        var cnt [26]int
        for k := 0; k < length; k++ {
            cnt[s1[i1+k]-'a']++
            cnt[s2[i2+k]-'a']--
        }
        for i := 0; i < 26; i++ {
            if cnt[i] != 0 {
                return false
            }
        }
        return true
    }

    var dfs func(i1, i2, length int) bool
    dfs = func(i1, i2, length int) bool {
        key := [3]int{i1, i2, length}
        if seen[key] {
            return memo[key]
        }
        seen[key] = true

        if s1[i1:i1+length] == s2[i2:i2+length] {
            memo[key] = true
            return true
        }
        if !sameCount(i1, i2, length) {
            memo[key] = false
            return false
        }

        for k := 1; k < length; k++ {
            if dfs(i1, i2, k) && dfs(i1+k, i2+k, length-k) {
                memo[key] = true
                return true
            }
            if dfs(i1, i2+length-k, k) && dfs(i1+k, i2, length-k) {
                memo[key] = true
                return true
            }
        }
        memo[key] = false
        return false
    }

    return dfs(0, 0, n)
}

复杂度分析

时间复杂度：$O(n^4)$。状态由三元组 $(i_1, i_2, len)$ 唯一确定，共 $O(n^3)$ 个；每个状态最多枚举 $len-1$ 个切点，并做一次 $O(len)$ 的字母计数与一次 $O(len)$ 的相等判断，单个状态的额外代价是 $O(n)$，相乘得到 $O(n^4)$。$n \le 30$ 时这个量级完全可以接受，而且计数剪枝会让实际访问到的状态远少于上界。

空间复杂度：$O(n^3)$。记忆化表本身就有 $O(n^3)$ 个格子，是空间的主项；递归深度不超过 $O(n)$，字母计数数组是常数级的 26 个格子，都可以忽略。

关键点总结

状态设计的核心技巧是「用等长性省掉一维」：两段互比的子串必然同长，所以三元组 $(i_1, i_2, len)$ 就够了，硬写成两个独立区间会白白多出一维。

交换分支的下标是这道题唯一需要动笔推的地方。s1 取前 $k$ 个字符时，交换意味着它要去匹配 s2 那一段的后 $k$ 个字符，起点是 $i_2 + len - k$，不是 $i_2 + k$。

记忆化必须把「假」也记下来。只缓存成功结果是初学者最常见的写法，它让剪枝完全失效，复杂度会退回指数级。

字母计数剪枝在理论上不改变复杂度上界，但它是这道题从超时到通过的分水岭。面试时要主动说出「这是必要不充分条件」，并能举出 "abcde" 与 "caebd" 这样的反例。

面试视角：这题真正在考「能否把一个看似组合爆炸的递归定义翻译成可枚举的状态」。先把递归定义原样写出来，再指出重复子问题，再压状态维度，最后补剪枝——这条叙述路径比直接写出三维数组更能体现思考过程。

易错点总结

错误写法：交换分支写成 dfs(i1, i2 + k, k) && dfs(i1 + k, i2, len - k)。用例 s1 = "great"、s2 = "rgeat" 里，判断 "gr" 对 "rg" 时这个写法退化成了不交换分支，f(0,0,2) 变为假，最终整体错判成 false。

错误写法：记忆化表用 boolean[][][]。默认值 false 和真实的假结果无法区分，要么把未计算的状态直接当成假返回，要么每次都重算，前者答案错、后者超时。

错误写法：只在结果为真时写入记忆化表。失败状态每次都要重跑完整的切点循环，s1 = "abcdbdacbdac" 这类长且计数处处相同的用例会直接超时。

错误写法：切点枚举写成 for (int k = 0; k < len; k++) 或 k <= len。$k=0$ 或 $k=len$ 会造出长度为 0 的子段，子问题规模不下降，递归无法收敛直至栈溢出。

错误写法：删掉「两段逐字符相同则返回真」这条基例，指望靠 $k$ 的循环递归到底。长度为 1 的状态里循环体一次都不执行，函数会直接返回假，s1 = "a"、s2 = "a" 就已经错了。

错误写法：把「字母计数相同」当成充要条件，直接返回计数比较的结果。用例 s1 = "abcde"、s2 = "caebd" 两边计数完全一致，正确答案是 false，这么写会错判成 true。

错误写法：用 s1.substring(...) + "#" + s2.substring(...) 拼成字符串当记忆化的键。每次建键都要付出 $O(len)$ 的复制和哈希，常数放大到几十倍，长用例上会超时。

错误写法：忘记开头的长度相等判断。s1 = "ab"、s2 = "abc" 会在计数或切分时越界抛异常。

错误写法：第三维数组只开到 n。len 的合法取值包含 $n$ 本身，根调用 dfs(0, 0, n) 会立刻数组越界。

错误写法：把两个子问题的关系写成「或」。不交换时必须左对左、右对右同时成立才算一种合法切分，写成或会让几乎所有输入都返回 true。

相似题目

题目	难度	考察点
312. 戳气球	困难	同样在区间上枚举分割点，但枚举的是「最后操作的位置」而非「第一刀切在哪」，转移是求最大值而不是布尔合取
1000. 合并石头的最低成本	困难	区间划分之外还要多带一维「当前合成了几堆」，切点枚举需要按步长跳跃
516. 最长回文子序列	中等	同为二维区间状态，但转移只看区间两端字符是否相等，不需要枚举内部切点