#131. 分割回文串

• LeetCode：原题
• 难度：中等
• 归类：字符串、动态规划、回溯
• 主解法：动态规划预处理 + 回溯

#先给结论

这是一道“枚举所有合法方案”的回溯题：从字符串左到右，枚举当前这一段的结束位置；如果这一段是回文串，就加入路径并继续分割剩余后缀。

为了避免在回溯过程中反复判断同一个子串是否为回文串，先用动态规划预处理：

isPalindrome[i][j] 表示 s[i...j] 是否为回文串

状态转移为：

isPalindrome[i][j]
= s[i] === s[j] && (j - i <= 2 || isPalindrome[i + 1][j - 1])

回溯负责“枚举所有切法”，动态规划负责“快速判断这一刀能不能切”。

#题目描述

给定一个字符串 s，将它分割成若干子串，使每个子串都是回文串。返回所有可能的分割方案。

回文串是正着读和反着读都相同的字符串。

示例：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

#问题本质

长度为 n 的字符串内部有 n - 1 个可能的切割位置，每个位置都有“切”或“不切”两种选择，因此最多需要考察 2^(n-1) 种切法。

字符串： a   a   b
切口：     ^   ^
           切/不切

不过，并非每种切法都合法。例如 "aab" 不切任何位置会得到 "aab"，它不是回文串。回溯可以在某一段不是回文串时立即剪枝，不再沿这条选择继续搜索。

核心问题可以拆成两部分：

1. 如何枚举所有分割方案：使用回溯。
2. 如何快速判断 s[start...end] 是否为回文串：使用动态规划预处理。

#一、动态规划预处理回文串

#1. 状态定义

isPalindrome[i][j] = s[i...j] 是否为回文串

这里的 i 和 j 都是闭区间下标。例如：

s = "aab"

isPalindrome[0][0] 表示 "a"
isPalindrome[0][1] 表示 "aa"
isPalindrome[0][2] 表示 "aab"

#2. 状态转移

一个子串是回文串，需要同时满足：

1. 首尾字符相同，即 s[i] === s[j]；
2. 去掉首尾字符后，中间部分也是回文串。

因此有：

isPalindrome[i][j]
= s[i] === s[j] && isPalindrome[i + 1][j - 1]

长度不超过 3 时，只要首尾相同，就一定是回文串：

• 长度为 1："a"；
• 长度为 2："aa"；
• 长度为 3："aba"，中间只有一个字符。

所以代码使用 j - i <= 2 处理基础情况：

s[i] === s[j] && (j - i <= 2 || isPalindrome[i + 1][j - 1]);

#3. 遍历顺序

isPalindrome[i][j] 依赖下一行的 isPalindrome[i + 1][j - 1]，因此 i 必须从大到小遍历，保证计算当前状态时，依赖状态已经得到结果。

i：n - 1 → 0
j：i → n - 1

#4. "aab" 的 DP 表

表格中 T 表示回文串，F 表示不是回文串，- 表示无效区间：

后续回溯只需查询这张表，就能用 O(1) 时间判断任意候选子串是否为回文串。

#和“最长回文子串”的动态规划有什么不同

两道题的回文状态定义和状态转移本质上是一样的，不同的是 DP 表计算完成后的用途。

#相同点：都在判断区间是否为回文串

两题通常都可以定义：

dp[i][j] = 闭区间子串 s[i...j] 是否为回文串

判断 s[i...j] 时，先比较首尾字符：

s[i] === s[j]

如果子串足够长，还需要检查去掉首尾后的内部区间：

dp[i + 1][j - 1]

所以两题的核心转移都可以写成：

dp[i][j] =
    s[i] === s[j] &&
    (j - i <= 2 || dp[i + 1][j - 1]);

例如判断 "ababa"：

"ababa" 是否回文
   ↓ 首尾 a === a
 "bab" 是否回文
   ↓ 首尾 b === b
  "a" 是回文

对应的依赖关系是：

dp[0][4] ← dp[1][3] ← dp[2][2]
 "ababa"    "bab"       "a"

#不同点一：DP 表的用途不同

最长回文子串只要求返回一个最长区间。每当发现 dp[i][j] === true 时，比较其长度并更新答案：

if (dp[i][j] && j - i + 1 > maxLength) {
    start = i;
    maxLength = j - i + 1;
}

分割回文串要求返回所有分割方案。DP 表本身不能直接生成这些方案，只用于回答回溯中的问题：

当前想选择 s[start...end]，它是不是回文串？

if (!isPalindrome[start][end]) {
    continue; // 这一段不能选
}

可以把两题的分工概括为：

因此，本题不是用 DP 计算“所有分割结果”，而是用 DP 预处理回溯需要反复查询的区间性质。

#不同点二：代码可能采用不同但等价的遍历顺序

最长回文子串常见的写法是按子串长度从短到长计算：

for (let length = 1; length <= n; length++) {
    for (let i = 0; i + length - 1 < n; i++) {
        const j = i + length - 1;
        dp[i][j] =
            s[i] === s[j] &&
            (length <= 3 || dp[i + 1][j - 1]);
    }
}

本文采用的是起点 i 从右向左计算：

for (let i = n - 1; i >= 0; i--) {
    for (let j = i; j < n; j++) {
        dp[i][j] =
            s[i] === s[j] &&
            (j - i <= 2 || dp[i + 1][j - 1]);
    }
}

看起来不同，但都遵守同一个原则：

在计算 dp[i][j] 之前，必须先算出它依赖的 dp[i + 1][j - 1]。

方式一：按长度递增
长度 1 → 长度 2 → 长度 3 → ……

方式二：起点倒序
i = n - 1 → n - 2 → …… → 0

两种顺序都正确，时间和空间复杂度也都是 O(n²)。

#j - i <= 2 为什么和其他实现不一样

有些最长回文子串代码会先把单字符状态初始化为 true，然后写：

s[i] === s[j] && (j - i <= 1 || dp[i + 1][j - 1])

本文没有单独初始化对角线，而是把长度为 1、2、3 的情况统一作为基础情况：

s[i] === s[j] && (j - i <= 2 || dp[i + 1][j - 1])

对于长度为 3 的 "aba"，只要首尾都是 a，中间的单字符 "b" 天然就是回文串，所以可以直接得到 true。

在本文的遍历顺序下，单字符状态也会提前计算出来，因此改成 j - i <= 1 || dp[i + 1][j - 1] 同样正确。<= 2 只是把长度为 3 的情况也直接判定了。这是基础条件的写法不同，并不是状态含义发生了变化。

#二、回溯枚举所有分割方案

#1. 回溯状态

• start：下一段子串的起始位置；s[0...start-1] 已经完成合法分割。
• path：当前已经选择的回文子串。
• result：所有完整的合法分割方案。

每次从 start 开始枚举结束位置 end：

s[start...end] 是回文串：选择它，递归处理 end + 1
s[start...end] 不是回文串：跳过这个 end

#2. "aab" 的完整搜索树

                         start = 0, path = []
                         剩余字符串："aab"
                         /                 \
                    选择 "a"             选择 "aa"
                    [0...0] ✓             [0...1] ✓
                      /                       \
          start = 1, path = ["a"]       start = 2, path = ["aa"]
               /             \                    |
          选择 "a"       尝试 "ab" ✗          选择 "b"
          [1...1] ✓       不是回文串             [2...2] ✓
              |                                      |
    start = 2, path = ["a","a"]       start = 3, path = ["aa","b"]
              |                                      |
          选择 "b"                                  收集结果
          [2...2] ✓                         ["aa","b"]
              |
    start = 3, path = ["a","a","b"]
              |
           收集结果
        ["a","a","b"]

根节点还会尝试 "aab"，但它不是回文串，因此直接跳过。

最后得到：

[
  ["a", "a", "b"],
  ["aa", "b"]
]

#3. 为什么需要撤销选择

当路径 ['a', 'a', 'b'] 搜索完成后，需要依次回到上层，尝试其他结束位置：

path.push(s.slice(start, end + 1)); // 作出选择
dfs(end + 1); // 搜索这个选择的后续方案
path.pop(); // 撤销选择，恢复进入本层前的状态

如果没有 path.pop()，上一条分支选择的子串会残留到下一条分支，导致结果混乱。

#代码实现

#JavaScript：动态规划 + 回溯

/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function (s) {
  const n = s.length;

  // isPalindrome[i][j] 表示闭区间子串 s[i...j] 是否为回文串
  const isPalindrome = Array.from({ length: n }, () => Array(n).fill(false));

  // 当前状态依赖下一行，因此起点 i 必须从后向前枚举
  for (let i = n - 1; i >= 0; i--) {
    for (let j = i; j < n; j++) {
      // 长度不超过 3 时，首尾相同即可；更长时还要保证内部为回文串
      isPalindrome[i][j] = s[i] === s[j] && (j - i <= 2 || isPalindrome[i + 1][j - 1]);
    }
  }

  const result = [];
  const path = [];

  const dfs = (start) => {
    // start 到达字符串末尾，说明 path 已经覆盖整个字符串
    if (start === n) {
      // 必须复制 path；后续回溯还会继续修改原数组
      result.push([...path]);
      return;
    }

    // 枚举当前这一段的结束位置
    for (let end = start; end < n; end++) {
      // 不是回文串就不能作为一段，直接尝试下一个结束位置
      if (!isPalindrome[start][end]) {
        continue;
      }

      // 选择 s[start...end]
      path.push(s.slice(start, end + 1));
      // 从 end + 1 开始分割剩余后缀
      dfs(end + 1);
      // 撤销选择，恢复现场后再尝试当前层的其他切法
      path.pop();
    }
  };

  dfs(0);
  return result;
};

#代码与思路对照

#正确性证明

可以从“不遗漏”和“不重复”两方面说明。

#不会遗漏合法方案

在任意位置 start，代码枚举了从 start 到字符串末尾的所有结束位置 end。合法方案的下一段一定对应其中某个 s[start...end]，并且回文表会将它标记为 true，所以该选择一定会被递归搜索。不断应用这个过程，任意合法分割方案都会到达 start === n 并被收集。

#不会加入非法方案或重复方案

只有 isPalindrome[start][end] 为 true 的子串才会加入 path，所以收集到的每一段都是回文串。每个方案的切割位置序列是唯一的，而一条递归路径唯一对应一组切割位置，因此同一个方案不会被重复生成。

#复杂度分析

设字符串长度为 n：

• 回文表预处理时间：O(n²)。
• 回文表空间：O(n²)。
• 回溯时间：最坏有 2^(n-1) 种分割方案；复制每个答案最多需要 O(n)，因此为 O(n × 2^n)。
• 回溯辅助空间：递归栈和 path 最深均为 O(n)。

综合来看：

• 时间复杂度：O(n² + n × 2^n)，通常简写为 O(n × 2^n)。
• 辅助空间复杂度：O(n²)，不计返回结果；若计入所有输出，最坏为 O(n × 2^n)。

这里的指数复杂度无法通过普通剪枝消除，因为题目要求返回全部方案，输出本身在最坏情况下就是指数级。

#边界与陷阱

• 忘记复制路径：应写 result.push([...path])，不能直接保存仍会被修改的 path。
• 忘记撤销选择：每次递归返回后必须 path.pop()。
• 切片右边界写错：slice 的右边界不包含在结果中，所以要写 slice(start, end + 1)。
• 回文区间定义混乱：本文的 isPalindrome[i][j] 使用闭区间，状态转移和循环边界都必须保持一致。
• DP 遍历方向错误：若 i 从小到大，读取 isPalindrome[i + 1][j - 1] 时它可能尚未计算。
• 只找到一个答案就返回：题目要求所有方案，收集一个答案后应回溯并继续搜索。
• 重复判断回文串：每次用双指针判断仍然可以通过，但会产生额外的重复扫描；预处理后查询只需 O(1)。

#面试官递进追问

#1. 为什么这题的主体是回溯，而不是单纯的动态规划？

题目要求返回所有具体分割方案，而不只是方案数或最优值。回溯用于构造并枚举每条路径；动态规划只负责预处理子串是否回文，帮助回溯剪枝。

#2. dfs(start) 的准确含义是什么？

s[0...start-1] 已经按照 path 完成合法分割，dfs(start) 负责枚举 s[start...n-1] 的所有合法分割方式。

#3. 为什么 i 要倒序遍历？

因为 isPalindrome[i][j] 依赖 isPalindrome[i + 1][j - 1]。倒序遍历 i 能保证下一行的状态先于当前行计算。

#4. 为什么基础条件是 j - i <= 2？

当首尾字符相同时，长度为 1 或 2 的字符串显然是回文串；长度为 3 时，中间只有一个字符，也必然是回文串。因此这些情况不需要访问内部区间。

#5. 能否不用 DP 表？

可以在每次选择前用双指针检查 s[start...end]，代码更直观、额外空间更少，但不同搜索分支会重复检查相同子串。也可以用记忆化搜索按需缓存回文判断结果。

#6. 如果只要求回文分割的最少次数呢？

问题会变成最优化 DP。可以在回文表的基础上定义 cuts[i] 为前缀 s[0...i] 的最少切割次数，而不需要枚举和保存所有路径。

#常见错误回答

• “这题用 DP”：没有说明 DP 只预处理回文状态，方案本身由回溯生成。
• 把 isPalindrome[i][j] 说成“前 i、j 个位置的答案”：状态定义不准确，无法推出转移方程。
• 只画出 ['a', 'a', 'b']：遗漏选择 "aa" 后得到的另一条路径。
• 复杂度只写 O(2^n)：遗漏构造、复制每个方案的成本，以及 O(n²) 的预处理。
• 把剪枝理解为“跳过更长的子串”：当前子串不是回文串，不代表扩大右边界后也一定不是回文串，所以只能 continue，不能 break。

#可迁移总结

• “返回所有方案”通常对应回溯；先定义路径含义，再枚举当前层的所有选择。
• 当回溯频繁查询相同区间性质时，可以先用 DP 预处理，或使用记忆化搜索。
• 回溯三步：作出选择 → 递归 → 撤销选择。
• 收集数组路径时要复制，否则保存的多个答案会引用同一个可变数组。
• 输出规模本身可能是指数级，因此复杂度分析要区分辅助空间和返回结果空间。

#刷题后自测

1. dfs(start) 中，start 之前和之后的字符串分别处于什么状态？
2. 为什么 isPalindrome[i][j] 的遍历顺序必须让 i 从大到小？
3. 在 "aab" 的搜索树中，哪两条路径能够到达 start === n？
4. 如果删除 path.pop()，第二条搜索路径会发生什么？
5. 为什么遇到一个非回文子串时只能 continue，不能 break？