题目描述
思路解析动画文字版
关键不是背模板，而是看懂为什么这题适合回溯 · 切割。
1. 枚举第一段切到哪：把 "aab" 切成若干段，每段都是回文。从位置 0 开始枚举：当前段先试最短 s[0..0]='a'。
2. 试 "a" → 单字符必回文：单字符天然回文 ✓ → 切下第一段 [a]，递归处理剩下的 "ab"。
3. 已切[a]，再试 "a"：绿色=已切下的段。在剩余里试 s[1]='a'，回文 ✓ → 切下 [a,a]，剩 "b"。
4. 切 "b" → 收集 [a,a,b]：试 s[2]='b'，回文 ✓，切到末尾 → 收集第一种方案 [a, a, b]。
5. 关键帧 · 试 "ab" 非回文 → 跳过：回溯到只切了 [a]。试更长的段 s[1..2]='ab'(蓝框)：左端 a、右端 b 不相等 → 不是回文 → 跳过这个切点。
6. 回开头试 "aa" → 回文：回到最开头，试更长的前缀 s[0..1]='aa'：左右两端都是 a 相等 → 是回文 → 切下 [aa]，剩 "b"。
7. 切 "b" → 收集 [aa,b]：剩下的 'b' 回文 ✓ → 收集第二种方案 [aa, b]。
8. 完成 · 2 种切法：整串 "aab" 试 "aab" 也非回文(a≠b)→跳过。最终 2 种切法：[[a,a,b],[aa,b]]，每段都是回文。
把这句话记住，下次遇到同类题，就能更快选出方向。
边界三连：边界三连：极端输入先过一遍。
几个高频追问，记住答法。
参考代码
class Solution: def partition(self, s): ans = [] def is_pal(l, r): while l < r: if s[l] != s[r]: return False l += 1; r -= 1 return True def backtrack(start, path): if start == len(s): ans.append(path[:]); return for end in range(start, len(s)): if is_pal(start, end): # 当前段回文才切 path.append(s[start:end+1]) backtrack(end + 1, path) path.pop() backtrack(0, []) return ans复杂度
- 时间复杂度：O(n·2^n)，最坏 2^(n-1) 种切法，每种判回文+构造 O(n)
- 空间复杂度：O(n)，递归深度 + path，O(n)（不计输出）
可套用的代码模板
模板不是死背，而是提醒你写代码前先把状态、转移和边界排好。
Python
# 分割回文串骨架 · 枚举切点def backtrack(start, path): if start == len(s): 收集 path; return for end in range(start, len(s)): if is_pal(s[start:end+1]): # 当前段是回文才切 path.append(s[start:end+1]) backtrack(end + 1, path) path.pop()易错点
面试追问把动画讲成自己的话
追问回溯怎么和判断回文结合？
追问怎么避免重复判断回文？
追问复杂度？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
电话号码的字母组合
LeetCode 17 · 中等 · 沿着 回溯 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题