LeetCode 131. 分割回文串
目录
题目描述
题意分析
给定字符串 s，把它切成若干段，要求每一段都是回文串，返回所有可行的切分方案。
先明确「切分」的含义：只能在相邻字符之间下刀，不能重排、不能删字符。所以一个方案就是若干个首尾相接的连续子串，拼起来必须恰好还原成 s，既不能漏也不能重叠。
再看题目要什么：不是问最少切几刀，也不是问方案有多少个，而是要把每一种方案的每一段字符串都列出来。返回的是完整方案集合，这就注定了算法的下界是方案数本身。
约束信号非常直白：s 的长度不超过 16，且只含小写字母。长度 16 意味着最多有 15 个可下刀的间隙，方案数上界是 $2^{15}$，也就是三万多种。这个数量级明确告诉你「把所有切法都枚举一遍」是被允许的，出题人要考的不是如何避免指数枚举，而是如何把枚举写得干净、剪得及时。
边界也要顺手确认：单个字符天然是回文，所以任何字符串都至少存在「全部拆成单字符」这一种方案，答案永远非空；s 长度为 1 时答案就是一个只含它自己的方案。
解法：回溯切分 + 回文预处理
核心思路
题目要求返回所有切分方案，指数级枚举无法避免；关键是只展开合法分支。令
dfs(start)枚举下一段的结束位置end，仅当s[start..end]是回文串时，才选择该段并递归到end + 1。回溯不变量：进入
dfs(start)时，path中的各段都是回文串，且拼接后恰好等于前缀s[0..start)。当start == n，说明整个字符串被无遗漏地切完，复制path即得到一个答案。每层枚举所有可能的end，因此不会漏解；一个切分对应唯一的端点序列，因此不会重复。为避免反复判断同一子串，先预处理
pal[i][j]：当两端字符相同，并且区间长度不超过 2，或内部区间也是回文时，该区间为回文。由于状态依赖pal[i + 1][j - 1]，i必须从后向前计算，之后回溯中的判断就是 $O(1)$。
解题步骤
- 建立
pal[n][n]，按i从大到小、j从i到n - 1的顺序预处理所有回文区间。- 从
dfs(0)开始；若start == n，复制当前路径到答案。- 枚举
end，跳过非回文区间s[start..end]。- 对回文区间执行“加入路径 → 递归
end + 1→ 撤销选择”。以
"aab"为例：起点 0 可以选择"a"或"aa"；继续递归分别得到["a","a","b"]和["aa","b"]。区间"aab"不是回文，直接剪枝。
代码实现
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<List<String>> partition(String s) {
int n = s.length();
boolean[][] pal = new boolean[n][n];
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
pal[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || pal[i + 1][j - 1]);
}
}
List<List<String>> res = new ArrayList<>();
dfs(0, s, pal, new ArrayList<>(), res);
return res;
}
private void dfs(int start, String s, boolean[][] pal, List<String> path, List<List<String>> res) {
if (start == s.length()) {
res.add(new ArrayList<>(path));
return;
}
for (int end = start; end < s.length(); end++) {
if (!pal[start][end]) {
continue;
}
path.add(s.substring(start, end + 1));
dfs(end + 1, s, pal, path, res);
path.remove(path.size() - 1);
}
}
}
func partition(s string) [][]string {
n := len(s)
pal := make([][]bool, n)
for i := range pal {
pal[i] = make([]bool, n)
}
for i := n - 1; i >= 0; i-- {
for j := i; j < n; j++ {
pal[i][j] = s[i] == s[j] && (j-i < 2 || pal[i+1][j-1])
}
}
res := make([][]string, 0)
path := make([]string, 0)
var dfs func(int)
dfs = func(start int) {
if start == n {
cur := append([]string(nil), path...)
res = append(res, cur)
return
}
for end := start; end < n; end++ {
if !pal[start][end] {
continue
}
path = append(path, s[start:end+1])
dfs(end + 1)
path = path[:len(path)-1]
}
}
dfs(0)
return res
}
复杂度分析
- 时间复杂度：$O(n^2 + n \cdot 2^n)$。预处理回文表为 $O(n^2)$；最坏情况下有指数级方案，每个方案的复制与字符串输出最多需要 $O(n)$。
- 空间复杂度：不计答案为 $O(n^2)$。回文表占 $O(n^2)$，递归栈和路径占 $O(n)$；答案本身最坏为 $O(n \cdot 2^n)$。
关键点总结
start表示已切分前缀的长度，使状态和终止条件都很清晰。- 回文表必须按
i倒序计算，保证内部区间已经得到结果。- 每次递归只选择回文前缀，返回后必须撤销；收集答案时必须复制路径。
- 回溯负责完整枚举，动态规划只优化回文判定，两者职责不同。
易错点总结
- 直接把可变的
path放入答案会被后续回溯修改，必须复制。- 递归起点应为
end + 1，否则同一字符被重复处理甚至无限递归。- 选择后忘记撤销，会让兄弟分支共享错误路径。
substring(start, end + 1)的右边界是开区间；非回文时应continue，不能终止整层搜索。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 5. 最长回文子串 | 中等 | 中心扩展求最长回文 |
| 78. 子集 | 中等 | 选与不选的回溯模板 |
| 93. 复原 IP 地址 | 中等 | 定段数分割 + 合法性剪枝 |
| 132. 分割回文串 II | 困难 | 最少切割次数的一维 DP |
| 140. 单词拆分 II | 困难 | 字典分割 + 记忆化搜索 |
| 647. 回文子串 | 中等 | 统计回文子串个数 |
| LCR 086. 分割回文串 | 中等 | 同型题的换皮版本 |
| LCR 094. 分割回文串 II | 困难 | 回文表配合线性 DP |