131. 分割回文串 (Medium)
专题归类： 08-回溯算法 LeetCode 链接： https://leetcode.cn/problems/palindrome-partitioning/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a"
输出：[["a"]]
提示：
1 <= s.length <= 16s仅由小写英文字母组成
题目详细分析
数据范围含义：
s.length <= 16：规模很小，2^15 = 32768 种分割方式，完全可枚举。- 仅含小写字母：简化了回文判断（大小写敏感性不是问题）。
核心问题转化：
- 本质是在字符串的 n-1 个间隔中决定是否切割（每个间隔切/不切两种选择），所以最多 2^(n-1) 种方案。
- 每个切割出来的子串必须是回文，这是剪枝条件。
回文判断方法：
- 双指针法：每次 O(n) 判断。
- 动态规划预处理：O(n^2) 预处理，O(1) 查询，适合多次判断的场景。
隐藏细节：
- 单个字符一定是回文串。
- 空串不是回文（但本题不会出现空子串）。
小白版直白理解
就像切香肠，一根字符串香肠，你要切成几段，要求每段从左到右读和从右到左读都一样（也就是回文）。你要列出所有可能的切法。
比如 “aab” 可以切成：
- a | a | b —— 每段都是一个字母，回文
- aa | b —— “aa” 是回文，“b” 是回文
但不能切成 a | ab，因为 “ab” 反过来是 “ba”，不同。
解题思路
思路一：回溯 + DP 预处理回文（推荐）
核心思想： 把问题看作”在字符串上选择切割点”。每次切割时判断当前子串是否为回文，如果是则继续切割剩余部分。先预处理所有子串的回文状态，让判断 O(1)。
决策树可视化（以 “aab” 为例）：
"aab"
/ \
切"a" 切"aa"
/ \
"ab" "b"
/ \ |
切"a" 切"ab"✗ 切"b"
/ 不是回文 |
"b" ✓ ["aa","b"]
|
✓ ["a","a","b"]
DP 回文预处理思路：
dp[i][j]表示s[i:j+1]是否为回文。- 递推：
s[i]==s[j] and (j-i<=2 or dp[i+1][j-1])。 - 从下往上、从左往右遍历。
def partition(s):
res = []
n = len(s)
# 预处理所有子串的回文状态
dp = [[False] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(i, n):
if s[i] == s[j] and (j - i <= 2 or dp[i + 1][j - 1]):
dp[i][j] = True
def backtrack(start, path):
# 已经切割到末尾，记录结果
if start == n:
res.append(path[:])
return
# 枚举当前切割的结束位置
for end in range(start, n):
if dp[start][end]: # O(1) 判断是否为回文
path.append(s[start:end + 1])
backtrack(end + 1, path)
path.pop()
backtrack(0, [])
return res思路二：回溯 + 双指针实时判断（无预处理版）
核心思想： 不使用 DP 预处理，每次用双指针判断子串是否为回文。代码更简单，但每次判断 O(n)。
def partition(s):
res = []
n = len(s)
def is_palindrome(l, r):
"""双指针判断 s[l:r+1] 是否为回文"""
while l < r:
if s[l] != s[r]:
return False
l += 1
r -= 1
return True
def backtrack(start, path):
if start == n:
res.append(path[:])
return
for end in range(start, n):
if is_palindrome(start, end): # 实时判断
path.append(s[start:end + 1])
backtrack(end + 1, path)
path.pop()
backtrack(0, [])
return res时间复杂度：
- DP 预处理版：O(n x 2^n)，预处理 O(n^2)，回溯 O(n x 2
- 无预处理版：O(n x 2^n x n) = O(n^2 x 2^n)，每次回文判断 O(n)。 空间复杂度： O(n^2)（DP 表）或 O(n)（递归栈，无预处理版）。
易错点
- 切割点枚举范围：
range(start, n)中end从 start 到 n-1，表示子串s[start:end+1]。越界是常见错误。 - 递归参数更新：切割完当前子串后，下一个 start 是
end + 1，而不是end。传错会导致无限递归或重复切割。 - DP 数组遍历顺序：
dp[i][j]依赖dp[i+1][j-1]（左下角），所以必须从下往上、从左往右遍历。顺序错了结果全错。 - 单个字符的处理：
j - i <= 2包含了j-i==0（单字符）和j-i==1（双字符相同），这两个都是回文。不要漏掉j-i==1的情况。 - slicing 效率：
s[start:end+1]创建新子串，O(k) 时间。如果十分在意性能，可以传 start 和 end 索引到最终再切。
框架提炼
切割类回溯问题模板：
def backtrack(start, path):
if start == len(s):
res.append(path[:])
return
for end in range(start, len(s)):
if 满足条件(s[start:end+1]):
path.append(s[start:end+1])
backtrack(end + 1, path) # 切割剩余部分
path.pop()切割 vs 组合的类比：
- 组合问题（如 78-子集）：从集合中选元素，start 控制不重复。
- 切割问题（如 131）：在字符串上选择切割点，start 控制切割起点，end 控制切割终点。
- 两者本质相同，都是
backtrack(i+1)的模式，只是”选择”的具体含义不同。
预处理技巧：
- 当回溯中需要频繁做某种 O(n) 判断时，可以提前 O(n^2) 预处理，将每次判断降到 O(1)。
- 本题预处理回文状态，类似地，在 5-最长回文子串中也用到 DP 预处理回文。