LeetCode 131. 分割回文串
题目描述
题意分析
把字符串
s从头到尾切成若干非空的连续子串，要求每一段从左到右和从右到左读都相同，并返回所有满足条件的切法。每个字符必须恰好属于一段，不能跳过、重复使用或改变顺序。这是枚举全部方案，不能在找到一种切法后停止，也不是求最少切割次数。长度为 $n$ 的字符串有 $n-1$ 个可切割间隙，最坏情况下每个间隙都能独立选择切或不切。题目给出 $n\le 16$，可以用回溯逐段枚举，并预先记录哪些区间是回文。
解法：回溯切分 + 回文预处理
核心思路
[!blue]
在下一段从
start开始时，依次尝试所有结束位置end，只把回文区间加入当前路径。不同前缀切法可能反复查询同一个区间是否回文，因此先用动态规划建立pal[i][j]，表示闭区间s[i..j]是否为回文，将搜索中的每次判断变为 $O(1)$。一个区间是回文，当且仅当两端字符相同，且去掉两端后的内部区间也是回文。长度为 $1$ 或 $2$ 时没有需要继续检查的内部区间，所以转移为：
\[pal[i][j]=(s[i]=s[j])\land\bigl(j-i<2\ \lor\ pal[i+1][j-1]\bigr)\]按左端点
i从大到小计算，依赖的第i+1行就已经就绪。代码中的短路或会先处理长度为 $1$、$2$ 的情况，不会访问不存在的内部区间。回溯状态
dfs(start)表示：path中每一段都是回文，它们恰好拼成前缀s[0..start)，start是第一个尚未分配的字符。选择s[start..end]后，下一段只能从end+1开始，这样既不重叠也不遗漏。递归返回后移除刚加入的段，恢复到选择前的状态，再尝试其他末尾。当
start == n时，路径已经完整覆盖字符串，复制它加入答案。任意合法切法都有唯一的一组分段末尾，回溯会逐一枚举到这些选择；反过来，只有回文段能进入路径，且只有覆盖完整字符串后才会记录。因此得到的恰好是所有合法切法，不会重复。
解题步骤
- 建立
pal[n][n]，按i从大到小、j从i到n - 1的顺序预处理所有回文区间。- 用空路径开始
dfs(0)。若start == n，复制当前路径到答案并返回，不能继续选择下一段。- 枚举
end从start到n - 1，用pal[start][end]判断候选段；不是回文就尝试下一个末尾。- 对回文区间执行“加入路径 → 递归
end + 1→ 移除当前段”，直到所有末尾都尝试完。每段至少包含一个字符，所以递归中的
start严格增加，最多深入 $n$ 层。单个字符一定是回文，因此沿着逐字符切分的分支始终能得到合法方案；某个较短区间不是回文，也不代表延长后的区间不是回文，不能提前结束当前循环。
代码实现
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)$ 个区间；当所有字符相同时，$n-1$ 个间隙的任意切法都合法，共有 $2^{n-1}$ 个答案，每份答案包含至多 $n$ 段。搜索、构造子串和复制路径的总开销由 $O(n\cdot 2^n)$ 限定。
- 空间复杂度：不计答案为 $O(n^2)$。回文表占 $O(n^2)$，递归栈和当前路径占 $O(n)$；全部答案本身最坏占 $O(n \cdot 2^n)$，这是返回所有方案所需的空间。
关键点总结
[!green]
- 回文表回答“这一段能否选”，回溯回答“选完这一段后，还能怎样完整切分”。
start左侧已经处理完毕，下一段固定从start开始，只需枚举结束位置。- 路径在分支之间复用，递归返回时撤销选择，保存答案时复制列表，两步分别保证分支与结果互不干扰。
易错点总结
[!yellow]
- 直接把可变的
path放入答案会被后续回溯修改，必须复制。- 递归起点应为
end + 1，否则同一字符被重复处理甚至无限递归。- 选择后忘记撤销，会让兄弟分支共享错误路径。
substring(start, end + 1)的右边界是开区间；非回文时应continue，不能终止整层搜索。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 132. 分割回文串 II | 困难 | 回文区间判定相同，原题求最少切割次数，本题输出所有合法划分。 |
| 647. 回文子串 | 中等 | 同样预处理或枚举回文子串，本题把这些区间作为划分搜索中的可选边。 |
| 5. 最长回文子串 | 中等 | 用区间或中心扩展刻画回文结构；本题预处理回文后枚举切分方案，该题寻找最长连续回文。 |
| 516. 最长回文子序列 | 中等 | 用区间或中心扩展刻画回文结构；本题预处理回文后枚举切分方案，该题允许跳过字符求最长回文子序列。 |