131. 分割回文串中等给你一个字符串s请你将s分割成一些 子串使每个子串都是回文串。返回s所有可能的分割方案。示例 1输入s aab 输出[[a,a,b],[aa,b]]示例 2输入s a 输出[[a]]提示1 s.length 16s仅由小写英文字母组成 核心笔记分割回文串 (选或不选 / 逗号切割法)1. 核心思想 (一句话总结)“手拿菜刀走到底每个字符后面切一刀还是连着走”我们遍历字符串的每一个字符索引 i对于 i 和 i1 之间的缝隙我们面临两个选择不切 (Join)当前子串还没结束继续往后看下一位。切 (Cut)当前子串[start, i]结束。前提是切下来的这段必须是回文串。图像记忆 (切香肠)你有一根香肠aab。走到第一个a后面不切等着凑个更大的比如aa。切切下来一块a它是回文合法然后处理剩下那截。2. 算法流程 (Input View)这也是典型的选或不选模型Binary TreeBase Casei n说明整个字符串处理完了收集结果。分支一不切 (Skip)条件i n - 1。因为最后一个字符后面必须完结不能悬在半空所以只有不是最后一个字符时才能选择“不切”。动作dfs(i 1, start)。start不变子串变长了。分支二切 (Pick)条件isPalindrome(start, i)。只有当前是回文才能切。动作记录子串dfs(i 1, i 1)。下一个子串从i1开始。回溯removeLast。 代码回忆清单 (带注释版)// 题目LC 131. Palindrome Partitioning class Solution { public ListListString partition(String s) { ListListString ans new ArrayList(); ListString path new ArrayList(); dfs(0, 0, s, path, ans); return ans; } // i: 当前正在考虑第 i 个字符 (作为潜在的结尾) // start: 当前子串的起始位置 private void dfs(int i, int start, String s, ListString path, ListListString ans) { // 1. Base Case: 走到字符串末尾 if (i s.length()) { ans.add(new ArrayList(path)); // 复制结果 return; } // 2. 分支 A: 不切 (Dont 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 也移到 i1 (新子串的起点) 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 aabDFS(0, 0): 指针在第一个 a。不切:DFS(1, 0)- start0, i1 (当前看着 aa)。切: a 是回文 -path[a]-DFS(1, 1)。分支DFS(1, 0)(刚才选择了不切现在看第二个 a)不切:DFS(2, 0)- start0, i2 (当前看着 aab)。切: aa 是回文 -path[aa]-DFS(2, 2)- 剩下 b - ... -[aa, b]。分支DFS(1, 1)(刚才切了第一个 astart1)不切:DFS(2, 1)- start1, i2 (当前看着 ab)。切: a 是回文 -path[a, a]-DFS(2, 2)- ... -[a, a, b]。(最终结果[aa, b], [a, a, b])