131. 分割回文串
中等
给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a"
输出：[["a"]]
提示：
- 1 <= s.length <= 16
- s 仅由小写英文字母组成
📝 核心笔记：分割回文串 (选或不选 / 逗号切割法)
1. 核心思想 (一句话总结)
“手拿菜刀走到底：每个字符后面，切一刀还是连着走？”
我们遍历字符串的每一个字符索引 i，对于 i 和 i+1 之间的缝隙，我们面临两个选择：
💡 图像记忆 (切香肠)：
- 你有一根香肠 aab。
- 走到第一个 a 后面：
-
- 不切：等着凑个更大的（比如 aa）。
- 切：切下来一块 a（它是回文，合法），然后处理剩下那截。
2. 算法流程 (Input View)
这也是典型的 选或不选 模型（Binary Tree）：
-
- 条件：i < n – 1。因为最后一个字符后面必须完结（不能悬在半空），所以只有不是最后一个字符时，才能选择“不切”。
- 动作：dfs(i + 1, start)。start 不变，子串变长了。
-
- 条件：isPalindrome(start, i)。只有当前是回文才能切。
- 动作：记录子串，dfs(i + 1, i + 1)。下一个子串从 i+1 开始。
- 回溯：removeLast。
🔍 代码回忆清单 (带注释版)
// 题目：LC 131. Palindrome Partitioning
class Solution {
public List<List<String>> partition(String s) {
List<List<String>> ans = new ArrayList<>();
List<String> path = new ArrayList<>();
dfs(0, 0, s, path, ans);
return ans;
}
// i: 当前正在考虑第 i 个字符 (作为潜在的结尾)
// start: 当前子串的起始位置
private void dfs(int i, int start, String s, List<String> path, List<List<String>> ans) {
// 1. Base Case: 走到字符串末尾
if (i == s.length()) {
ans.add(new ArrayList<>(path)); // 复制结果
return;
}
// 2. 分支 A: 不切 (Don't Split)
// 只有不到最后一位时，才能选择"不切"继续连
// 如果到了最后一位(n-1)，必须切，否则字符串就没结束
if (i < s.length() – 1) {
// i 往前移，但 start 不动 (子串在变长)
dfs(i + 1, start, s, path, ans);
}
// 3. 分支 B: 切 (Split)
// 只有 [start, i] 是回文串时，才有资格切这一刀
if (isPalindrome(s, start, i)) {
path.add(s.substring(start, i + 1));
// i 往前移，start 也移到 i+1 (新子串的起点)
dfs(i + 1, i + 1, s, path, ans);
path.removeLast(); // 回溯
}
}
// 标准双指针判断回文
private boolean isPalindrome(String s, int left, int right) {
while (left < right) {
if (s.charAt(left++) != s.charAt(right–)) {
return false;
}
}
return true;
}
}
⚡ 快速复习 CheckList (易错点)
- [ ] 对比标准解法 (For循环枚举)？
-
- 你的解法 (二叉树)：每个缝隙选/不选。递归深度 。
- 标准解法 (N叉树)：站在 start，枚举终点 j (从 start 到 n)。
- 结论：你的解法逻辑严密，但在 Java 中因为 substring 的存在，效率相差不大。面试中两种皆可，标准解法代码略短一些。
- [ ] 边界条件 i < n – 1？
-
- 这是此解法的命门。
- 如果 i 到了最后一个字符，你不能选择“不切”，因为那样会导致递归结束时，最后一段 substring 没被加入 path，字符串被“吞”了一截。
- [ ] 回文判断优化？
-
- 目前 isPalindrome 是 。整个算法接近 。
- 如果字符串很长，可以用 动态规划 (DP) 预处理一个 boolean[][] isPal 表，把判断降为 。
🖼️ 数字演练
输入 s = "aab"
-
- 不切: DFS(1, 0) -> start=0, i=1 (当前看着 "aa")。
- 切: "a" 是回文 -> path=["a"] -> DFS(1, 1)。
-
- 不切: DFS(2, 0) -> start=0, i=2 (当前看着 "aab")。
- 切: "aa" 是回文 -> path=["aa"] -> DFS(2, 2) -> 剩下 "b" -> … -> ["aa", "b"]。
-
- 不切: DFS(2, 1) -> start=1, i=2 (当前看着 "ab")。
- 切: "a" 是回文 -> path=["a", "a"] -> DFS(2, 2) -> … -> ["a", "a", "b"]。
(最终结果：["aa", "b"], ["a", "a", "b"])
