LeetCode 131. 分割回文串——回溯+预处理DP判断回文的O(n²)优化
LeetCode 131. 分割回文串——回溯+预处理DP判断回文的O(n²)优化
适读人群：Java中级工程师、算法进阶者 | 阅读时长：约22分钟 | 难度：中等
开篇故事
分割回文串这道题是回溯和动态规划的完美结合题。纯回溯可以解，但每次判断子串是否为回文需要 O(n) 时间，整体效率不高；预处理一个二维 DP 数组记录所有子串的回文状态，可以将每次回文判断从 O(n) 降到 O(1)，总复杂度从 O(n² × 2^n) 降到 O(n² + n × 2^n)。
这道题让我第一次深刻感受到"预处理"的力量——提前花 O(n²) 时间和空间，换来后续每次 O(1) 的查询，是一笔非常划算的买卖。很多题目（判断最长公共子串、最短路径等）都有类似的思路：用空间换时间，预计算所有需要的子结果。
一、题目解析
题目： 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。
示例：
- 输入：s = "aab"，输出：[["a","a","b"],["aa","b"]]
- 输入：s = "a"，输出：[["a"]]
回溯思路： 枚举所有可能的分割位置，每次取 [start, i] 的子串，如果是回文串则加入当前路径，继续从 i+1 开始分割。
朴素判断回文： 对子串 s[l..r]，双指针从两端向中间逼近，O(r-l+1) 时间。
DP 预处理： 用二维数组 isPalin[l][r] 记录 s[l..r] 是否为回文，转移方程：
isPalin[l][r] = (s[l] == s[r]) && (r-l <= 1 || isPalin[l+1][r-1])- 预处理时间 O(n²)，之后每次查询 O(1)。
二、解法一：回溯+暴力判断回文
代码
import java.util.*;
public class Solution_Basic {
private List<List<String>> result = new ArrayList<>();
public List<List<String>> partition(String s) {
backtrack(s, 0, new ArrayList<>());
return result;
}
private void backtrack(String s, int start, List<String> path) {
if (start == s.length()) {
result.add(new ArrayList<>(path));
return;
}
for (int end = start; end < s.length(); end++) {
// 判断 s[start..end] 是否为回文（O(end-start+1)时间）
if (isPalindrome(s, start, end)) {
path.add(s.substring(start, end + 1));
backtrack(s, end + 1, path);
path.remove(path.size() - 1);
}
}
}
private boolean isPalindrome(String s, int l, int r) {
while (l < r) {
if (s.charAt(l) != s.charAt(r)) return false;
l++; r--;
}
return true;
}
}复杂度分析
- 时间复杂度： O(n × 2^n)——共 O(2^n) 种分割方案，每次判断回文 O(n)，记录结果 O(n)。
- 空间复杂度： O(n) 递归栈 + O(n) 路径。
三、解法二：回溯+DP预处理（最优解）
DP预处理思路
用 boolean[][] isPalin = new boolean[n][n] 预先计算所有子串的回文状态。
注意枚举顺序： 转移方程 isPalin[l][r] = (s[l]==s[r]) && isPalin[l+1][r-1] 依赖于 isPalin[l+1][r-1]（长度更短的子串），所以要按子串长度从短到长枚举（或者按 l 从大到小、r 从小到大）。
代码
import java.util.*;
public class Solution {
private List<List<String>> result = new ArrayList<>();
private boolean[][] isPalin;
public List<List<String>> partition(String s) {
int n = s.length();
isPalin = new boolean[n][n];
// DP 预处理：计算所有子串的回文状态
// 方法：按 l 从右到左，r 从 l 到 n-1 枚举（保证 l+1 先于 l 计算）
for (int l = n - 1; l >= 0; l--) {
for (int r = l; r < n; r++) {
if (s.charAt(l) == s.charAt(r) && (r - l <= 1 || isPalin[l+1][r-1])) {
isPalin[l][r] = true;
}
}
}
backtrack(s, 0, new ArrayList<>());
return result;
}
private void backtrack(String s, int start, List<String> path) {
if (start == s.length()) {
result.add(new ArrayList<>(path));
return;
}
for (int end = start; end < s.length(); end++) {
if (isPalin[start][end]) { // O(1) 查询
path.add(s.substring(start, end + 1));
backtrack(s, end + 1, path);
path.remove(path.size() - 1);
}
}
}
}Mermaid 图：DP预处理与回溯的配合
复杂度分析
- 时间复杂度： O(n²) 预处理 + O(n × 2^n) 回溯 = O(n × 2^n)（回溯主导）。
- 注意： 虽然渐进复杂度相同，但实际运行中 O(1) 替换 O(n) 的回文查询，在 n 较大时有明显加速（因为回文查询在回溯中被调用次数是 O(n × 2^n)，总查询时间从 O(n² × 2^n) 降到 O(n × 2^n)）。
- 空间复杂度： O(n²) 预处理矩阵 + O(n) 递归栈。
四、解法三：记忆化（Manacher + 回溯）
Manacher 算法简介
Manacher 算法可以在 O(n) 时间内计算字符串的所有回文子串。但对于这道题，Manacher 比 DP 更复杂，实际收益不大（DP 已经是 O(n²)，Manacher 是 O(n)，但回溯本身是 O(n × 2^n)，预处理的差异不影响总体复杂度）。
更实用的优化：在 DP 基础上，对回溯进行"剪枝"——如果当前分割已经无法完成（剩余字符串没有任何合法分割方案），提前剪枝。
实现方式：预处理 canPartition[i] = s[i..n-1] 是否能被分割为若干回文串，如果 !canPartition[start] 可以直接剪枝。
// 预处理 canPartition（从右到左）
boolean[] canPartition = new boolean[n + 1];
canPartition[n] = true; // 空字符串可以被分割
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if (isPalin[i][j] && canPartition[j + 1]) {
canPartition[i] = true;
break;
}
}
}
// 在 backtrack 中加入剪枝
if (!canPartition[start]) return; // 剩余部分无法分割，直接返回完整代码：
import java.util.*;
public class Solution_V3 {
private List<List<String>> result = new ArrayList<>();
private boolean[][] isPalin;
private boolean[] canPartition;
public List<List<String>> partition(String s) {
int n = s.length();
isPalin = new boolean[n][n];
canPartition = new boolean[n + 1];
// DP 计算回文状态
for (int l = n - 1; l >= 0; l--) {
for (int r = l; r < n; r++) {
if (s.charAt(l) == s.charAt(r) && (r - l <= 1 || isPalin[l+1][r-1])) {
isPalin[l][r] = true;
}
}
}
// 预处理 canPartition（判断 s[i..n-1] 是否能被分割为若干回文串）
canPartition[n] = true;
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if (isPalin[i][j] && canPartition[j + 1]) {
canPartition[i] = true;
break;
}
}
}
backtrack(s, 0, new ArrayList<>());
return result;
}
private void backtrack(String s, int start, List<String> path) {
if (start == s.length()) {
result.add(new ArrayList<>(path));
return;
}
if (!canPartition[start]) return; // 剪枝：剩余部分无法形成全回文分割
for (int end = start; end < s.length(); end++) {
if (isPalin[start][end]) {
path.add(s.substring(start, end + 1));
backtrack(s, end + 1, path);
path.remove(path.size() - 1);
}
}
}
}复杂度分析
- 时间复杂度： O(n²) 预处理 + O(n × 结果数量)，canPartition 剪枝在有些情况下能显著减少回溯节点数。
- 空间复杂度： O(n²)，两个预处理数组。
五、举一反三
相关题目
LeetCode 132. 分割回文串 II 给字符串 s，最少分割多少次，使每个子串都是回文。只需统计最少次数，用 DP（不用回溯）。
LeetCode 1278. 分割回文串 III 将 s 分成 k 段，最少总修改字符数使每段都是回文。二维DP。
DP 预处理回文的模板
// 预处理 isPalin[l][r] 的标准写法
int n = s.length();
boolean[][] isPalin = new boolean[n][n];
for (int l = n - 1; l >= 0; l--) { // l 从右往左
for (int r = l; r < n; r++) { // r 从左往右（r >= l）
isPalin[l][r] = (s.charAt(l) == s.charAt(r))
&& (r - l <= 1 || isPalin[l+1][r-1]);
}
}这个模板适用于所有需要"O(1)查询任意子串是否为回文"的场景。
六、踩坑实录
坑一：DP 枚举顺序错误
isPalin[l][r] 依赖于 isPalin[l+1][r-1]，即 l 更大、r 更小的状态。因此必须让 l 的计算顺序从大到小（l 从 n-1 到 0），否则在计算 isPalin[l][r] 时，isPalin[l+1][r-1] 可能还没有被计算。
// 错误：l 从 0 开始，依赖的 l+1 状态还没计算
for (int l = 0; l < n; l++) { ... } // 错误！
// 正确：l 从 n-1 开始
for (int l = n - 1; l >= 0; l--) { ... } // 正确坑二：子串提取的端点
s.substring(start, end + 1) 注意 Java 的 substring 是左闭右开区间，取 [start, end] 的子串需要 end + 1，不是 end。
坑三：r - l <= 1 的边界条件
当子串长度为 1（l == r）或长度为 2（r == l+1）时，不需要检查 isPalin[l+1][r-1]（因为长度1的子串必然是回文，长度2的子串只要两端字符相等就是回文）。条件 r - l <= 1 处理了这两种情况。
坑四：path.add(s.substring(start, end+1)) 与回溯
path 中存的是 String（不可变），所以 path.remove(path.size() - 1) 直接移除对象引用即可，不需要担心 String 被修改。这与存 int 的情况类似，比存 List 的子集/组合要简单。
七、总结
分割回文串展示了"回溯+预处理"的经典模式：
- 识别子问题：每次分割需要判断子串是否为回文，这是一个重复计算的子问题。
- 预处理：用 O(n²) 的 DP 预计算所有子串的回文状态，存入二维数组。
- O(1) 查询：在回溯过程中直接查表，避免重复计算。
这种"预处理换速度"的思想，在很多回溯和动态规划题中都有应用，是中高级算法题的常见优化手段。
| 解法 | 时间复杂度 | 空间复杂度 | 推荐 |
|---|---|---|---|
| 回溯+暴力回文 | O(n² × 2^n) | O(n) | 不推荐 |
| 回溯+DP预处理 | O(n × 2^n) | O(n²) | 推荐 |
| 回溯+DP+canPartition剪枝 | O(n × 结果数) | O(n²) | 最优 |
补充深入讲解：回文判断预处理与回溯分割的协作设计
DP 预处理的必要性分析
在没有预处理的情况下，每次回溯过程中检查 s[l..r] 是否为回文，需要从两端向中心比较，时间复杂度是 O(r-l+1)。在最坏情况下（比如全 a 组成的字符串），回溯树有 2^(n-1) 个节点，每个节点的分割检查最多需要 O(n)，总时间复杂度是 O(2^n × n)。
通过 DP 预处理所有 isPalin[l][r]，预处理时间是 O(n²)，空间是 O(n²)。在回溯时，每次回文检查变成 O(1)（直接查表）。这将总时间复杂度降低到 O(2^n)，对于 n<=16 的约束，从约 10^7×16 次操作降低到约 10^5 次操作，提升了约 10 倍。
预处理的价值在于"把多次计算的公共子问题一次性解决"。isPalin[l][r] 在不同的回溯路径中可能被多次查询（比如 s[0..3] 在很多分割方案中都会被检查），预处理只计算一次，后续所有查询 O(1)，是典型的"时间换时间"优化（用预处理时间换后续查询时间）。
DP 递推关系的正确性证明
isPalin[l][r] = (s[l] == s[r]) && (r - l <= 1 || isPalin[l+1][r-1])
证明：字符串 s[l..r] 是回文，当且仅当：
- s[l] == s[r]（首尾字符相同），且
- s[l+1..r-1] 是回文（去掉首尾后的子串也是回文）
对于 r - l <= 1 的情况（字符串长度为 1 或 2），不需要递归检查更短的子串：
- 长度 1（l == r）：单个字符一定是回文。
- 长度 2（r == l+1）：只要两个字符相同（s[l] == s[r]），就是回文；不相同则不是。
这两种情况都被 r - l <= 1 覆盖，此时只要 s[l] == s[r] 就返回 true，不用再检查内部（内部为空或已经是单字符）。
递推的计算顺序必须是"从短子串到长子串"：先计算所有长度为 1 的子串，再计算长度为 2 的，以此类推。代码中用两层循环：外层 length 从 1 到 n，内层 l 从 0 到 n-length，r = l + length - 1。这样保证计算 isPalin[l][r] 时，isPalin[l+1][r-1] 已经计算完毕。
回溯分割的剪枝分析
分割回文串的回溯有一个自然的剪枝：如果 s[start..i] 不是回文，直接跳过，不需要继续向更深的层递归。这是回溯的基本特性，通过 if (!isPalin[start][i]) continue; 实现。
更进一步的剪枝是利用 DP 预处理的信息提前终止：如果从 start 开始，没有任何回文子串可以延伸到足够远的位置，使得剩余部分也能被分割成回文串，则可以提前回退。但这个剪枝难以在代码中简洁表达，实际上基本剪枝已经足够高效。
对于特殊输入（如全同字符的字符串 "aaa...a"），所有子串都是回文，分割数量是 2^(n-1)，此时无法剪枝，必须枚举所有 2^(n-1) 种分割方案。这是最坏情况，时间复杂度 O(2^n × n)。在 n<=16 时可以接受，若 n 更大则需要其他方法。
Manacher 算法：O(n) 的回文检测
对于需要更快回文检测的场景，Manacher 算法能在 O(n) 时间内计算所有以每个位置为中心的最长回文子串，从而在 O(n) 时间内预处理所有子串的回文性。
Manacher 的核心思想是利用"回文的对称性"：如果已知一个长回文 C 的范围是 [l, r]，则 C 内部的每个位置 i 对应的回文半径，至少等于其关于 C 的对称点 j=2c-i 的回文半径（在不超出 [l,r] 范围的前提下）。这个对称性避免了从头重新计算，使得总时间复杂度降为 O(n)。
在 LeetCode 131 这道题中，由于 n<=16，O(n²) 的 DP 预处理已经足够快，不需要 Manacher 算法。但在需要处理更长字符串的变形题中，Manacher 是不可或缺的工具。
分割问题的推广
分割回文串是"分割字符串使每段满足某种性质"这类问题的典型代表。推广的问题形式：将字符串分割为最少段数，使每段都满足性质 P（回文、单调、字典序最小等）。
这类问题通常有 DP 解法（求最少段数）和回溯解法（枚举所有分割方案）。当只需要最少段数时，DP 在 O(n²) 时间内完成（对于回文分割，即 LeetCode 132，最少分割次数 = 最少分割段数 - 1）。当需要枚举所有方案时，回溯不可避免，时间复杂度与方案数相关。
回溯分割问题的通用框架
分割回文串（LeetCode 131）是"分割类回溯"问题的代表，与"组合类回溯"和"排列类回溯"并列为回溯的三大经典模型。
分割类回溯的框架是：遍历当前起点 start 到末尾的所有可能切割点 i，如果 s[start..i] 满足某种性质（本题是回文），则把这段加入路径，递归处理 s[i+1..end]，递归返回后撤销选择。
这个框架与组合类回溯非常相似（都用 start 参数标记当前处理起点），区别在于：组合类从 candidates 数组中选元素，分割类从字符串中截取子串。两者都通过 start 参数保证了处理的有序性，避免了重复枚举。
分割类问题的常见变形：分割字符串使每段都是整数（且没有前导零）、分割字符串使每段长度满足某种约束、IP 地址分割（每段是 0-255 的整数，恰好分四段）。这些变形都使用相同的分割类回溯框架，只是"满足性质"的判断条件不同。
DP 预处理与回溯协作的设计模式
分割回文串中，DP 预处理（判断所有子串是否为回文）与回溯（枚举所有分割方案）的协作，体现了一种重要的设计模式：用 DP 消除重复计算，用回溯枚举所有方案。
更一般地说，当回溯过程中某个判断（如"s[l..r]是否为回文"）在不同的回溯分支中被多次调用，且每次计算的代价不可忽略时，可以用记忆化（memoization）或 DP 预处理来缓存结果，避免重复计算。
这种"DP+回溯"的混合方法在竞赛中很常见，也是面试中展示高级算法理解的好机会。关键是识别出"哪个子问题会被重复计算"，然后选择合适的缓存策略（HashMap 记忆化或 DP 表格预处理）。
分割回文串中，isPalin[l][r] 是被重复查询的子问题，选择 DP 表格（O(n²) 空间）而不是 HashMap 记忆化，是因为所有子问题的范围是固定的（l 和 r 都在 [0, n-1] 内），表格方式访问更高效（没有哈希开销），且可以按长度递增的顺序填表（自下而上 DP）。
分割回文串的变形题预防
LeetCode 131 有一个经典变形：LeetCode 132（分割回文串 II），要求找到最少的分割次数，使每个子串都是回文。这道题不需要枚举所有方案，只要求最优解的数量（最少分割次数），因此可以用动态规划解决：dp[i] 表示 s[0..i] 的最少分割次数，dp[i] = min(dp[j-1]+1) 对所有满足 s[j..i] 是回文的 j，时间复杂度 O(n²)。
两道题形成了很好的对比：131 枚举所有方案（回溯），132 求最少次数（动态规划）。通过这对题目，可以感受"枚举型问题用回溯，最优化型问题用 DP"这个基本原则的适用场景。
在面试中，131 和 132 有时会被配合考查：先问 131（枚举所有分割方案），再问"如果只要求最少分割次数怎么办"（引出 DP 解法）。这种"先枚举再优化"的考法，考查了候选人从回溯到 DP 的思维转换能力。
回文的高效判断方法回顾
本文介绍了两种回文判断方法：朴素双指针（O(n)每次）和 DP 预处理（O(n²)预处理，O(1)查询）。还有第三种方法：字符串哈希（Rolling Hash）。
字符串哈希可以在 O(n) 时间预处理，然后 O(1) 判断任意子串 s[l..r] 是否为回文：先对字符串和其反转分别计算哈希前缀数组，然后比较 s[l..r] 的哈希值与 s[l..r] 反转的哈希值。哈希方法的缺点是有极低的哈希碰撞概率（需要双重哈希降低误判率），但优点是预处理更快，且更容易推广到大字符集的情况。
在面试中，DP 预处理是首选（无哈希碰撞风险，代码清晰），字符串哈希在竞赛中常用（更快的预处理，更易推广）。了解两种方法各自的适用场景，体现了对算法权衡的成熟理解。
分割回文串的两个核心技术——DP 预处理回文和分割类回溯框架——是处理所有分割字符串满足某种性质问题的通用模板，值得深刻理解并内化为自己的算法工具箱。
分割回文串把 DP 和回溯结合，是算法综合运用的典型示例，值得反复练习。
掌握了回文判断的 DP 预处理和分割类回溯框架，就掌握了这类问题的通解。