知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 06 - 分割回文串 ## 题目(LeetCode 131) 给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。返回所有可能的分割方案。 ``` 输入:"aab" 输出:[["a","a","b"], ["aa","b"]] ``` ## 大白话理解 在字符串的不同位置切几刀,让切出来的每一段都是回文。 切割问题本质上就是组合问题:在哪些位置切一刀? ``` 字符串 "aab" 可以切的位置:a | a | b 切法 1:a | a | b → ["a", "a", "b"] 每段都是回文 ✓ 切法 2:a | ab → ["a", "ab"] "ab" 不是回文 ✗ 切法 3:aa | b → ["aa", "b"] 每段都是回文 ✓ 切法 4:aab → ["aab"] "aab" 不是回文 ✗ ``` ## 决策树 ``` "aab" startIndex=0: 切出 "a"(回文✓) 切出 "aa"(回文✓) 切出 "aab"(✗跳过) | | startIndex=1: 切出 "a"(✓) "ab"(✗) 切出 "b"(✓) | | startIndex=2: 切出 "b"(✓) 结束 → ["aa","b"] | 结束 → ["a","a","b"] ``` ## 代码 ```java class Solution { private List<List<String>> result = new ArrayList<>(); public List<List<String>> partition(String s) { backtrack(s, 0, new ArrayList<>()); return result; } private void backtrack(String s, int startIndex, List<String> path) { // 切到末尾了,说明整个字符串都被成功分割 if (startIndex == s.length()) { result.add(new ArrayList<>(path)); return; } for (int i = startIndex; i < s.length(); i++) { // 从 startIndex 到 i 切一刀,得到子串 s[startIndex..i] String sub = s.substring(startIndex, i + 1); if (!isPalindrome(sub)) continue; // 不是回文,跳过(剪枝) path.add(sub); // 做选择 backtrack(s, i + 1, path); // 从 i+1 继续切 path.remove(path.size() - 1); // 撤销选择 } } private boolean isPalindrome(String s) { int left = 0, right = s.length() - 1; while (left < right) { if (s.charAt(left++) != s.charAt(right--)) return false; } return true; } } ``` > 💬 **Q:没有理解,增加树形图解释** > > 用 `s = "aab"` 完整演示决策树。每个节点表示"当前从哪个位置开始切",每条边表示"切出了哪个子串"。 > > ``` > 根节点:startIndex=0,还没切任何东西,path=[] > > startIndex=0 > / | \ > 切"a"(回文✓) 切"aa"(回文✓) 切"aab"(非回文✗) > / | > startIndex=1 startIndex=2 > path=["a"] path=["aa"] > / \ \ > 切"a"(✓) 切"ab"(✗) 切"b"(✓) > | | > startIndex=2 startIndex=3 > path=["a","a"] path=["aa","b"] > \ > 切"b"(✓) > | > startIndex=3 > path=["a","a","b"] > ↓ > 到达末尾,收集结果 ✓ > > 最终结果:[["a","a","b"], ["aa","b"]] > ``` > > **逐步对应代码:** > > ``` > 第 1 层:startIndex=0,for i 从 0 到 2 > i=0:sub = s[0..0] = "a",是回文 ✓ > path=["a"],递归进入第 2 层(startIndex=1) > i=1:sub = s[0..1] = "aa",是回文 ✓ > path=["aa"],递归进入第 2 层(startIndex=2) > i=2:sub = s[0..2] = "aab",不是回文 ✗,continue 跳过 > > 第 2 层(从 startIndex=1 开始):for i 从 1 到 2 > i=1:sub = s[1..1] = "a",是回文 ✓ > path=["a","a"],递归进入第 3 层(startIndex=2) > i=2:sub = s[1..2] = "ab",不是回文 ✗,continue 跳过 > > 第 3 层(从 startIndex=2 开始):for i 从 2 到 2 > i=2:sub = s[2..2] = "b",是回文 ✓ > path=["a","a","b"],递归进入第 4 层(startIndex=3) > > 第 4 层:startIndex=3 == s.length()=3,到达末尾 > 收集结果:["a","a","b"] ✓,return > > 回溯:path 依次撤销 "b"→"a"→"a",回到第 1 层继续 i=1 > > 第 2 层(从 startIndex=2 开始,path=["aa"]):for i 从 2 到 2 > i=2:sub = s[2..2] = "b",是回文 ✓ > path=["aa","b"],递归进入第 3 层(startIndex=3) > > 第 3 层:startIndex=3 == s.length()=3,到达末尾 > 收集结果:["aa","b"] ✓,return > ``` > > **关键理解:** > - `startIndex` 是"下一刀从哪里开始切",每次递归都往右推进 > - `i` 控制"这一刀切到哪里结束",`s[startIndex..i]` 就是这一段 > - 不是回文就 `continue` 跳过,不进入递归(剪枝) > - 到达末尾(`startIndex == s.length()`)说明整个字符串切完了,收集结果 ### 怎么理解"切割 = 组合"? ``` 字符串 "aab",长度 3 组合问题的视角:从 [0,1,2] 中选择切割点 选 0~0, 1~1, 2~2 → "a", "a", "b" 选 0~1, 2~2 → "aa", "b" startIndex 就是当前切割的起点 i 就是当前切割的终点 s[startIndex..i] 就是切出来的子串 ``` ### 优化:预处理回文判断 每次调用 `isPalindrome` 都要 O(n),可以用动态规划预处理。 ```java // 预处理:dp[i][j] 表示 s[i..j] 是否是回文 boolean[][] dp = new boolean[n][n]; for (int i = n - 1; i >= 0; i--) { for (int j = i; j < n; j++) { if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) { dp[i][j] = true; } } } // 回溯中用 dp[startIndex][i] 替代 isPalindrome ``` ## 复杂度 - 时间:O(n × 2^n),最坏情况所有子串都是回文(如 "aaa") - 空间:O(n) ## 一句话总结 切割问题 = 组合问题。startIndex 是切割起点,i 是切割终点,切出来的子串是回文才继续。 --- 上一篇:[05 - 电话号码的字母组合](./05-letter-combinations.md) | 下一篇:[07 - N 皇后](./07-n-queens.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入