当前位置：首页 > news >正文

131. 分割回文串

news 2026/5/12 13:24:55

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 之间的缝隙，我们面临两个选择：

不切 (Join)：当前子串还没结束，继续往后看下一位。
切 (Cut)：当前子串[start, i]结束。前提是：切下来的这段必须是回文串。

💡图像记忆 (切香肠)：

你有一根香肠aab。
走到第一个a后面：

- 不切：等着凑个更大的（比如aa）。
- 切：切下来一块a（它是回文，合法），然后处理剩下那截。

2. 算法流程 (Input View)

这也是典型的选或不选模型（Binary Tree）：

Base Case：i == n，说明整个字符串处理完了，收集结果。
分支一：不切 (Skip)：

- 条件：i < n - 1。因为最后一个字符后面必须完结（不能悬在半空），所以只有不是最后一个字符时，才能选择“不切”。
- 动作：dfs(i + 1, start)。start不变，子串变长了。

分支二：切 (Pick)：

- 条件：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; } }