#87. 扰乱字符串

• LeetCode：原题1
• 难度：困难
• 归类：动态规划（字符串、动态规划）
• 主解法：动态规划（区间 DP）

#先给结论

这道题的核心是把原问题拆成有依赖关系的子问题，保存子问题答案以避免重复计算。面试时先说清楚“状态表示什么、为什么能排除其他候选、何时更新答案”，再写代码；只报出“用 动态规划”还不足以证明理解。

#题目描述

题目要求完成“扰乱字符串”。输入包括 s1（string）、s2（string），需要返回 boolean。完整限制以原题为准，解题时重点利用这些特征：字符串、动态规划。

示例：

输入：s1 = "great", s2 = "rgeat"
输出：true
解释：s1 上可能发生的一种情形是：
"great" --> "gr/eat" // 在一个随机下标处分割得到两个子字符串
"gr/eat" --> "gr/eat" // 随机决定：「保持这两个子字符串的顺序不变」
"gr/eat" --> "g/r / e/at" // 在子字符串上递归执行此算法。两个子字符串分别在随机下标处进行一轮分割
"g/r / e/at" --> "r/g / e/at" // 随机决定：第一组「交换两个子字符串」，第二组「保持这两个子字符串的顺序不变」
"r/g / e/at" --> "r/g / e/ a/t" // 继续递归执行此算法，将 "at" 分割得到 "a/t"
"r/g / e/ a/t" --> "r/g / e/ a/t" // 随机决定：「保持这两个子字符串的顺序不变」
算法终止，结果字符串和 s2 相同，都是 "rgeat"
这是一种能够扰乱 s1 得到 s2 的情形，可以认为 s2 是 s1 的扰乱字符串，返回 true

#1.dp 数组含义

输入是 s1（string）、s2（string）。dp[i][j] 表示处理到前 i、j 个位置（或二维坐标 i、j）时的子问题答案；具体维度与代码中的两个状态参数一一对应。状态必须能够直接推出题目最终答案，不能只把 dp 笼统说成“缓存”。

#2. 确定状态转移方程

枚举当前可做的选择，把问题转移到规模更小且已经可求的状态，再根据题意取最大值、最小值、求和或判断可行性。其因果链是：旧状态已经正确 → 当前选择补上最后一步 → 合并得到当前状态。参考实现中的分支就是这条转移方程的代码形式。

#3.dp 数组如何初始化

初始化来自状态定义：空前缀、越界位置或没有作出选择时使用题目的单位值；不可能状态使用 Infinity、-Infinity 或明确的哨兵。不要为了“方便”统一填 0，否则最值类问题可能把不可达状态当成合法答案。

#4. 确定遍历顺序

计算当前状态时，它依赖的更小状态已经按遍历顺序计算完成。表格 DP 要让被依赖的行、列先计算；记忆化搜索则由递归按需展开，并在返回前写入缓存。若做一维空间压缩，遍历方向还要保证本轮不会覆盖仍需读取的旧状态。

#5. 举例打印dp 数组

示例：

输入：s1 = "great", s2 = "rgeat"
输出：true
解释：s1 上可能发生的一种情形是：
"great" --> "gr/eat" // 在一个随机下标处分割得到两个子字符串
"gr/eat" --> "gr/eat" // 随机决定：「保持这两个子字符串的顺序不变」
"gr/eat" --> "g/r / e/at" // 在子字符串上递归执行此算法。两个子字符串分别在随机下标处进行一轮分割
"g/r / e/at" --> "r/g / e/at" // 随机决定：第一组「交换两个子字符串」，第二组「保持这两个子字符串的顺序不变」
"r/g / e/at" --> "r/g / e/ a/t" // 继续递归执行此算法，将 "at" 分割得到 "a/t"
"r/g / e/ a/t" --> "r/g / e/ a/t" // 随机决定：「保持这两个子字符串的顺序不变」
算法终止，结果字符串和 s2 相同，都是 "rgeat"
这是一种能够扰乱 s1 得到 s2 的情形，可以认为 s2 是 s1 的扰乱字符串，返回 true

手算时至少核对一个基础状态和一次非平凡转移；它们与代码一致，才说明状态定义成立。

#代码实现

参考实现来源：JoshCrozier/leetcode-javascript，按本文结构重新整理；原项目采用 MIT License。

#JavaScript 实现

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var isScramble = function(s1, s2) {
  const n = s1.length;
  const dp = new Array(n).fill().map(() => new Array(n).fill().map(() => new Array(n).fill(null)));

  function dfs(i1, j1, i2) {
    if (dp[i1][j1][i2] !== null) {
      return dp[i1][j1][i2];
    }
    if (i1 == j1) {
      return dp[i1][j1][i2] = s1[i1] === s2[i2];
    }

    const j2 = j1 - i1 + i2;
    let result = false;
    for (let i = i1; i < j1; i++) {
      result = result || (dfs(i1, i, i2) && dfs(i + 1, j1, i2 + i - i1 + 1))
        || (dfs(i1, i, j2 - i + i1) && dfs(i + 1, j1, i2));
    }

    return dp[i1][j1][i2] = result;
  }

  return dfs(0, n - 1, 0);
};

#代码与思路对照

读代码时应把每个判断还原成“它排除了什么状态或完成了哪次转移”，而不是只记变量名。

#复杂度分析

• 时间复杂度：O(n^4)。
• 空间复杂度：O(n^3)。

复杂度必须按“状态数量 × 每个状态处理成本”分析；如果存在排序、堆操作、递归深度或结果数组，需要单独计入，不能只看最外层循环。

#面试官递进追问

#1. 为什么本题适合 动态规划？

因为把原问题拆成有依赖关系的子问题，保存子问题答案以避免重复计算。 为什么问： 检查你是在识别性质，还是只凭题号背模板。回答要抓住可被利用的单调性、重复子问题或数据结构约束。

#2. 代码维护的核心状态是什么？

状态表示处理到某个位置、区间或选择状态时能够得到的最优值或方案数。 为什么问： 状态定义决定代码是否可证明。回答时要让每个变量都能对应到题意。

#3. 这个实现依赖什么不变量？

计算当前状态时，它依赖的更小状态已经按遍历顺序计算完成。 为什么问： 不变量比逐行复述代码更能证明理解，回答要说明它在初始化、推进和结束时都成立。

#4. 为什么这样推进不会漏掉答案？

枚举当前选择，由已知状态通过转移方程更新下一状态或当前最优值，被跳过的状态已经由题目性质证明不可能更优或已经处理完成。 为什么问： 检查正确性证明，重点不是“指针这样写”，而是“为什么可以排除”。

#5. 最危险的边界是什么？

最容易错在状态定义含糊、初始化与定义不一致，以及一维压缩后的遍历方向错误。 为什么问： 检查代码能否一次通过，回答要给出具体失败场景而不是只说“注意边界”。

#6. 复杂度还能优化吗？

先看瓶颈来自状态数量、每次转移成本还是辅助结构操作；只有其中一项能被减少时，复杂度才可能继续下降。 为什么问： 检查你能否从成本组成出发优化，而不是机械背最优复杂度。

#7. 如果输入规模扩大或数据改成流式，方案怎么变？

要判断当前算法是否需要随机访问全部输入；若只依赖有限历史状态，可以做滚动或在线维护，否则需要分块、外存或调整数据结构。 为什么问： 检查算法理解能否迁移到工程约束。

#8. 有哪些替代解法，如何取舍？

可以从暴力枚举开始，再比较排序、哈希、搜索或动态规划等方案；取舍标准是时间、空间、是否修改输入和实现复杂度。 为什么问： 检查横向比较能力。回答要说明替代方案为什么更慢或在什么条件下更合适。

#常见错误回答

• “这题套 动态规划 模板即可”：只有结论，没有说明题目性质和排除依据。
• 逐行朗读代码：没有建立状态、不变量和正确性因果链。
• 只报 O(n) 或 O(n²)：没有解释每个状态被访问多少次，也容易漏掉排序或辅助结构。
• 把示例能跑通当成证明：示例只能帮助检查，不能覆盖重复值、空输入和极端边界。

#可迁移总结

• 核心关键词：动态规划、状态定义、不变量、推进规则、边界。
• 一句话本质：把原问题拆成有依赖关系的子问题，保存子问题答案以避免重复计算。
• 思考链路：识别题目性质 → 定义状态 → 证明推进安全 → 确定更新时机 → 检查边界与复杂度。
• 1 分钟回答：说清题型、核心状态、推进规则和复杂度。
• 3 分钟回答：补上正确性依据、示例和两个关键边界。
• 10 分钟回答：写出代码，并比较替代方案、空间优化和工程限制。

#刷题后自测

先只回答第 1 题，再展开后续问题：

1. 不看代码，你能用一句话说出本题的不变量吗？

2. 如果把示例中的重复值、空输入或边界值换掉，哪一行代码最先受到影响？

3. 不改变正确性的前提下，你能写出一种替代方案并比较复杂度吗？