LeetCode LCR 086. 分割回文串
目录
题目描述
题意分析
给一个字符串
s，把它切成若干段，要求每一段都是回文串，返回所有可能的切法。注意是「所有方案」而不是「方案数」也不是「最少段数」，所以必须把每一种切法真正构造出来。
先看清楚问题的结构。长度为
n的串有n - 1个「缝隙」，每个缝隙可以切或不切，因此总切法有 $2^{n-1}$ 种，我们要从中筛出「每段都回文」的那些。这说明本题本质是在一维序列上枚举分割点，与在数组上枚举子集是同一类骨架，区别只在于每段要额外通过一次合法性检验。
约束
1 ≤ s.length ≤ 16且只含小写字母。$2^{15} = 32768$ 种切法，规模极小，指数枚举完全可行。但这个上界也提醒：如果每次判断一段是否回文都花 $O(n)$ 时间，最坏总量是 $O(n \cdot 2^n)$，虽然仍能过，但「回文判断会被反复重复地问同一个问题」这个浪费是本题真正想让你发现的点。
边界：单字符必然是回文，所以「逐字符全切开」永远是一个合法答案，因此答案列表绝不会为空；
n = 1时唯一答案是[["a"]]；不同的分割点集合必然给出不同的方案，所以不需要去重，即便串里全是相同字符（如"aaaa"）也不会产生重复方案。
解法：哈希表统计状态
核心思路
朴素做法是：从位置 0 出发，枚举第一段的结尾
j，检查s[0..j]是否回文，是则递归处理s[j+1..]。瓶颈出在检查上——搜索树上会反复问「s[2..5]是不是回文」这种完全相同的问题，同一个区间在不同的分支里被验证很多次，每次都要 $O(n)$。
关键观察是：「某个区间是否回文」只与区间本身有关，与它出现在哪条搜索路径上无关，因此可以先把全部 $O(n^2)$ 个区间的答案一次性算出来存表，搜索时 $O(1)$ 查表。
这张表本身也有递推结构。记
f[i][j]表示s[i..j]（闭区间）是否回文，则有f[i][j] = (s[i] == s[j]) && f[i+1][j-1]：首尾字符相同，且去掉首尾后的内部也回文。递推的依赖方向是「短区间推长区间」，而f[i+1][j-1]的行号比f[i][j]大、列号比它小，所以外层i必须倒序遍历，内层j从i+1正序遍历，才能保证用到的值已经算好。
长度为 1 和 2 的区间是递推的起点。把整张表初始化为
true一并解决了这两种情形：i == j的单字符格子不会被循环覆盖，保持true正确；j == i + 1时公式里的f[i+1][j-1]落在i+1 > j-1的「空区间」格子上，其初值true恰好表示「空串是回文」，于是f[i][i+1]正确地等于s[i] == s[i+1]。这个初始化技巧免掉了所有特判。
有了表之后，搜索的不变量就很清晰：
dfs(i)表示s[0..i-1]已经被切成若干回文段并记录在t中，当前要决定从下标i开始的这一段切到哪里。每层横向枚举结尾j从i到n-1，只在f[i][j]为真时才向下递归dfs(j+1)。i == n说明整串切完，t就是一个完整方案。
解题步骤
- 先建回文表：
f是n × n的布尔矩阵，全部初始化为true。初值不是随便填的——它同时承担了「单字符回文」和「空区间回文」两个基准情形，是后面公式无需特判的原因。
- 倒序填表：
for (int i = n - 1; i >= 0; --i)配for (int j = i + 1; j < n; ++j)，执行f[i][j] = s.charAt(i) == s.charAt(j) && f[i + 1][j - 1]。i必须倒序，因为f[i][*]依赖f[i+1][*]；j从i + 1起，因为j == i的对角线已由初值给出。
- 递归基：
dfs(i)中i == n表示所有字符都被覆盖，深拷贝t存入答案。这里用i == n而不是i >= n，因为j + 1最大恰为n，不会越过。
- 枚举当前段的结尾：
for (int j = i; j < n; ++j)。j从i开始意味着允许长度为 1 的段，这是「答案永远非空」的保障；j取到n - 1意味着允许「剩下的整体作为一段」。
- 查表剪枝并递归：只有
f[i][j]为真才把s.substring(i, j + 1)压入t并递归dfs(j + 1)，返回后弹出。j + 1是下一段的起点，写成j会让同一个字符被切进两段。
以
s = "aab"走一遍，n = 3。
建表：初值全
true。i = 2时内层不执行。i = 1：j = 2，f[1][2] = (s[1] == s[2]) && f[2][1] = ('a' == 'b') && true = false。i = 0：j = 1，f[0][1] = ('a' == 'a') && f[1][0] = true && true = true；j = 2，f[0][2] = ('a' == 'b') && f[1][1] = false。于是回文区间为[0,0]、[1,1]、[2,2]、[0,1]，即"a"、"a"、"b"、"aa"。
搜索从
dfs(0)开始，t = []。j = 0：f[0][0]为真，切出"a"，t = ["a"]，进入dfs(1)。
dfs(1)：j = 1，f[1][1]为真，切出"a"，t = ["a","a"]，进入dfs(2)；dfs(2)中j = 2，f[2][2]为真，切出"b"，t = ["a","a","b"]，进入dfs(3)，i == n命中，记下第一个答案["a","a","b"]。回溯弹出"b"、弹出"a"。回到dfs(1)的j = 2：f[1][2]为假（"ab"不回文），跳过。dfs(1)结束，弹出"a"，回到dfs(0)。
dfs(0)的j = 1：f[0][1]为真，切出"aa"，t = ["aa"]，进入dfs(2)；其中j = 2切出"b"，进入dfs(3)命中，记下第二个答案["aa","b"]。回溯弹出。dfs(0)的j = 2：f[0][2]为假（"aab"不回文），跳过。
最终答案
[["a","a","b"], ["aa","b"]]。若把递归写成dfs(j)而非dfs(j + 1)，第一段切出"a"后又从下标 0 开始，会产出["a","a","a","b"]这种字符被重复使用的错误方案，甚至陷入死循环。
代码实现
class Solution {
private int n;
private String s;
private boolean[][] f;
private List<String> t = new ArrayList<>();
private List<List<String>> answer = new ArrayList<>();
public List<List<String>> partition(String s) {
n = s.length();
f = new boolean[n][n];
// 全部初始化为 true：同时给出「单字符回文」与「空区间回文」两个基准。
for (int i = 0; i < n; ++i) {
Arrays.fill(f[i], true);
}
// i 倒序：f[i][j] 依赖行号更大的 f[i + 1][j - 1]。
for (int i = n - 1; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
f[i][j] = s.charAt(i) == s.charAt(j) && f[i + 1][j - 1];
}
}
this.s = s;
dfs(0);
return answer;
}
// i：当前待切分段的起点，s[0..i-1] 已切好并记录在 t 中。
private void dfs(int i) {
if (i == s.length()) {
answer.add(new ArrayList<>(t));
return;
}
for (int j = i; j < n; ++j) {
if (f[i][j]) {
t.add(s.substring(i, j + 1));
// 下一段从 j + 1 开始，写成 j 会让字符被重复使用。
dfs(j + 1);
t.remove(t.size() - 1);
}
}
}
}
func partition(s string) (answer [][]string) {
n := len(s)
f := make([][]bool, n)
// 全部初始化为 true：同时给出「单字符回文」与「空区间回文」两个基准。
for i := range f {
f[i] = make([]bool, n)
for j := range f[i] {
f[i][j] = true
}
}
// i 倒序：f[i][j] 依赖行号更大的 f[i+1][j-1]。
for i := n - 1; i >= 0; i-- {
for j := i + 1; j < n; j++ {
f[i][j] = s[i] == s[j] && f[i+1][j-1]
}
}
t := []string{}
// i：当前待切分段的起点，s[0..i-1] 已切好并记录在 t 中。
var dfs func(int)
dfs = func(i int) {
if i == n {
answer = append(answer, append([]string(nil), t...))
return
}
for j := i; j < n; j++ {
if f[i][j] {
t = append(t, s[i:j+1])
// 下一段从 j+1 开始，写成 j 会让字符被重复使用。
dfs(j + 1)
t = t[:len(t)-1]
}
}
}
dfs(0)
return
}
复杂度分析
- 时间复杂度：$O(n \times 2^n)$。预处理回文表是 $O(n^2)$，被搜索部分吞掉。搜索树最多有 $2^{n-1}$ 条完整路径（每个缝隙切或不切），每条路径在递归基处需要 $O(n)$ 拷贝方案，路径上的
substring累计也是 $O(n)$。回文判断因为查表已降为 $O(1)$，不再贡献额外因子。- 空间复杂度：$O(n^2)$，主要来自
n × n的回文表；递归栈深度与t的长度都不超过n。返回值按惯例不计入。
关键点总结
- 「同一个子问题在搜索树上被反复问到」是引入预处理表的标准信号。把与路径无关的判定提前算好，是搜索优化最常用也最容易讲清楚的一招，面试时主动提出这一点比直接写朴素判断高一个层次。
- 回文区间表的递推方向由依赖关系决定：
f[i][j]依赖f[i+1][j-1]，所以i倒序、j正序。凡是二维区间 DP，先画出依赖箭头再定循环方向，是通用的做法。- 把表初始化为
true一次性覆盖了长度 0 和 1 两个基准，让主公式无需任何特判。这种「用初值吸收边界」的技巧在区间 DP 里很常见，值得刻意积累。- 枚举分割点的骨架是
dfs(i)枚举段尾j、递归dfs(j+1)，它是一切「把序列切成满足某性质的若干段」题目的公共模板，换掉合法性判断即可复用。- 本题不需要去重：不同的分割点集合必然对应不同的方案，即使输入是
"aaaa"也不会重复。判断要不要去重，看的是「不同选择序列会不会产出相同结果」。
易错点总结
- 递归写成
dfs(j)而不是dfs(j + 1)：s = "aab"会不断从同一位置重切，产出["a","a","a","b"]这类字符被复用的方案，甚至栈溢出。- 填表时
i写成正序：s = "aba"计算f[0][2]时f[1][1]尚未定型（虽然初值为true侥幸正确），但s = "abba"计算f[0][3]需要的f[1][2]还没算，会读到初值true，把"abba"之外的非回文也判成回文。- 回文表不初始化为
true而是默认false：s = "aa"时f[0][1] = ('a'=='a') && f[1][0] = true && false = false，"aa"被误判为非回文，答案会漏掉["aa"]。substring的右端写成j：s = "aab"第一段会取到空串""，答案里混入空字符串段。- 忘记
t.remove(t.size() - 1)：s = "aab"产出["a","a","b"]后残留不清，第二个方案变成["a","a","b","aa","b"]。- 把
t的引用直接存入answer：s = "aab"最终得到两个空列表[[],[]]，因为搜索结束时共享的t已被清空。- Go 里写
answer = append(answer, t)不做拷贝：["a","a","b"]存入后底层数组被后续append覆写，输出变成重复的乱值。- 递归基写成
i >= n却在循环里让j越界：若把内层循环写成j <= n，s[i:j+1]在j == n时会越界 panic。- 每层现场用双指针判回文而不预处理：
s = "aaaaaaaaaaaaaaaa"（16 个 a）时同一个区间会被重复判定上万次，虽然仍能通过，但面试官追问「有没有重复计算」时答不上就是失分点。- 误以为需要对答案排序或去重：
s = "aaa"的三个方案本就互不相同，额外加Set既无必要，还会因为List<String>的哈希开销拖慢运行。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 131. 分割回文串 | 中等 | 与本题完全同题，代码可原样提交 |
| 132. 分割回文串 II | 困难 | 只求最少切割次数，回文表照用但搜索换成线性 DP，规模可放大到 2000 |
| LCR 094. 分割回文串 II | 困难 | 与 132 同题，是本题「枚举全部方案」到「只要最优值」的直接对照 |
| 647. 回文子串 | 中等 | 只统计回文子串个数，把本题的预处理表求和即可，不需要搜索 |
| 5. 最长回文子串 | 中等 | 求最长的单个回文区间，同一张表上取最大跨度，或用中心扩展省空间 |
| 93. 复原 IP 地址 | 中等 | 同为「枚举分割点」骨架，合法性判断换成数值范围与前导零 |
| 139. 单词拆分 | 中等 | 段的合法性由词典决定，只问能否拆分，用一维可达性 DP 而非枚举方案 |
| 140. 单词拆分 II | 困难 | 要输出全部拆分方案，与本题骨架一致，需配合记忆化避免指数级重算 |