LeetCode 131分割回文串是回溯算法Backtracking的经典题把字符串切成若干子串要求每个子串都是回文求所有切法。核心思路从前往后切每次从当前位置“start” 往后枚举终点“end”回文判断如果“s[start:end1]” 是回文就可以作为一段递归把这段加入路径继续切后面的部分回溯递归返回后把这段从路径里拿掉尝试别的切法终止条件“start” 走到字符串末尾说明切完了一整串记录结果方法一回溯 实时判断回文最直观面试首选from typing import Listclass Solution:def partition(self, s: str) - List[List[str]]:res []path [] # 当前的一种分割方案def is_palindrome(sub: str) - bool: 判断子串是否为回文 return sub sub[::-1] def backtrack(start: int): # 切到末尾说明找到了一种合法分割 if start len(s): res.append(path[:]) # 注意要拷贝 return # 枚举当前起点能切出的所有子串 for end in range(start, len(s)): sub s[start:end1] if is_palindrome(sub): path.append(sub) # 做选择 backtrack(end 1) # 递归切后面的 path.pop() # 撤销选择回溯 backtrack(0) return res方法二回溯 DP 预处理回文表性能更优如果字符串很长频繁切片判断回文会慢。可以提前用 DP 算出所有子串是否回文回溯时 O(1) 查询。from typing import Listclass Solution:def partition(self, s: str) - List[List[str]]:n len(s)res []path []# 1. 预处理dp[i][j] 表示 s[i..j] 是否为回文 dp [[False] * n for _ in range(n)] for i in range(n): for j in range(i, n): if s[i] s[j] and (j - i 2 or dp[i1][j-1]): dp[i][j] True # 2. 回溯 def backtrack(start: int): if start n: res.append(path[:]) return for end in range(start, n): if dp[start][end]: path.append(s[start:end1]) backtrack(end 1) path.pop() backtrack(0) return res复杂度分析项目 说明时间复杂度 最坏情况全“‘a’” 字符串接近“O(2ⁿ)”因为每个位置都可以切或不切共“2ⁿ” 种方案每份拷贝“O(n)”空间复杂度“O(n)” 递归栈深度不计结果存储DP 版额外“O(n²)” 存储回文表易错点 面试 Tips✅“res.append(path[:])” 一定要拷贝直接“append(path)” 会因为后续“pop” 导致结果被改空✅ 回文判断别用双指针写错边界“sub[::-1]” 最简单直观面试时也可以用双指针✅ 剪枝意识如果不是回文就直接跳过不要往下递归✅ DP 预处理公式“dp[i][j] (s[i]s[j]) and (j-i2 or dp[i1][j-1])”这是所有回文 DP 的基石跑个示例sol Solution()print(sol.partition(“aab”))输出: [[“a”,“a”,“b”], [“aa”,“b”]]要不要我顺便讲一下 LeetCode 132分割回文串 II那题求最少分割次数思路从回溯直接升级到 DP是这道题目的经典进阶。