扰乱字符串 | 每日算法

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

使用下面描述的算法可以扰乱字符串 s 得到字符串 t：

如果字符串的长度为 1，算法停止；
如果长度 > 1：在某个下标将 s 分成两个非空子串 x 和 y（s = x + y），再随机选择保持 x + y 或交换为 y + x，并对 x、y 递归执行本算法。

给你两个长度相等的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。

示例 1

输入：s1 = "great", s2 = "rgeat"

输出：true

可通过多次分割与（可选）交换子串，把 "great" 扰乱成 "rgeat"。

示例 2

输入：s1 = "abcde", s2 = "caebd"

输出：false

示例 3

输入：s1 = "a", s2 = "a"

输出：true

💭 模拟答题者思考

1. 暴力：枚举所有分割与是否交换的递归树——状态空间巨大，但子问题重复：同样是「s1 的某连续段能否变成 s2 的某连续段」，只与起点和长度有关。

2. 重复在哪里？固定起点 (i,j) 与长度 k，无论上层如何分割，答案唯一 → 记忆化 dfs(i,j,k) 或三维 dp[i][j][k]。

3. 转移直觉：第一次把长度 k 切成左 p、右 k-p。若不交换，左对左、右对右；若交换，s1 的左段要对上 s2 的右段、s1 的右段对上 s2 的左段（下标用 j+k-p 对齐）。

4. 剪枝：两段字符 multiset 必须相同（排序后相等或 26 字母计数），否则直接 false，避免无效枚举。

5. 边界 k=1：单字符能否扰乱 = 是否相等。按长度从小到大填表或自顶向下记忆化，总复杂度约 O(n⁴)（n³ 状态 × 每层 O(n) 分割）。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`dfs(i, j, k)` / `dp[i][j][k]`	bool	定义：`s1[i : i+k]` 能否经扰乱算法变成 `s2[j : j+k]` 维护：长度 `k=1` 时比首字符；`k>1` 时枚举分割点 `p∈[1,k)`，尝试「不交换」或「交换」两段子串的两种拼接方式更新：任一 `p` 使左右子问题同时为真则当前为真；否则为假
`p`	int	定义：当前长度 `k` 的子串在第一次分割时左段长度维护：`1 ≤ p < k`，左段长 `p`、右段长 `k-p` 更新：不交换：`dfs(i,j,p)∧dfs(i+p,j+p,k-p)`；交换：`dfs(i,j+k-p,p)∧dfs(i+p,j,k-p)`

⌨️ 落码步骤

1. 若 len(s1)≠len(s2) 返回 false；令 n=len(s1)

2. 定义 dfs(i,j,k)：k==1 时返回 s1[i]==s2[j]；若两段排序后不等返回 false

3. 枚举 p=1..k-1：若 dfs(i,j,p) and dfs(i+p,j+p,k-p)（不交换）或 dfs(i,j+k-p,p) and dfs(i+p,j,k-p)（交换）成立，返回 true

4. 全部 p 失败则 false；入口 dfs(0,0,n)（配合 @cache 或三维 DP 表）

💻 代码实现

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        n = len(s1)
        if n != len(s2):
            return False

        from functools import lru_cache

        @lru_cache(maxsize=None)
        def dfs(i: int, j: int, k: int) -> bool:
            if k == 1:
                return s1[i] == s2[j]
            if sorted(s1[i : i + k]) != sorted(s2[j : j + k]):
                return False
            for p in range(1, k):
                # 不交换：左对左、右对右
                if dfs(i, j, p) and dfs(i + p, j + p, k - p):
                    return True
                # 交换：s1 左段 ↔ s2 右段
                if dfs(i, j + k - p, p) and dfs(i + p, j, k - p):
                    return True
            return False

        return dfs(0, 0, n)

class Solution {
public:
    bool isScramble(string s1, string s2) {
        int n = s1.size();
        if (n != (int)s2.size()) return false;

        vector<vector<vector<char>>> dp(
            n, vector<vector<char>>(n, vector<char>(n + 1, 0)));

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                dp[i][j][1] = (s1[i] == s2[j]);

        for (int k = 2; k <= n; k++) {
            for (int i = 0; i + k <= n; i++) {
                for (int j = 0; j + k <= n; j++) {
                    bool ok = false;
                    for (int p = 1; p < k && !ok; p++) {
                        if ((dp[i][j][p] && dp[i + p][j + p][k - p]) ||
                            (dp[i][j + k - p][p] && dp[i + p][j][k - p]))
                            ok = true;
                    }
                    dp[i][j][k] = ok;
                }
            }
        }
        return dp[0][0][n];
    }
};
// 时间 O(n⁴)，空间 O(n³)；可在转移前加字符计数剪枝

📈 复杂度分析

时间复杂度 O(n⁴)

空间复杂度 O(n³)

⚠️ 常见坑

❗ 「交换」时 s2 左段起点是 j + k - p，不是 j + p——右段长度仍是 p，与 s1 左段对齐。

❗ 忘记字符 multiset 剪枝：字母组成不同必为 false，否则会多算大量无效 p。

❗ 分割点 p 必须满足 1 ≤ p < k，两段都非空；k=1 不能进分割循环。

🔍 必测边界 Case

Case 1：单字符相同/不同

s1="a", s2="a" → true；s1="a", s2="b" → false

Case 2：字母相同但无法扰乱

s1="abc", s2="bca" → false（计数相同仍可能无解）

Case 3：完全相同

s1="abcd", s2="abcd" → true（始终可选「不交换」一路到底）

Case 4：经典 true

s1="great", s2="rgeat" → true