从分割回文串看回溯算法与缓存优化：LeetCode 131全解

刷 LeetCode 的时候我有个习惯先把题目归类。131 这道题光看名字“分割回文串”很多人以为是个字符串处理题其实骨子里是一道回溯题。今天这篇题解基于 Python 实现重点不是把 AC 代码甩出来而是把“回溯 cache 缓存”这条优化路径讲透。题目本身不难但如果你能想清楚 cache 到底缓存什么、为什么加、加在哪一层你就能把这一套方法迁移到很多“枚举所有方案”的题目上比如复原 IP 地址、单词拆分、分割回文串 II 这类变体。先给还没做过 131 的同学一个交代给定一个字符串 s要求把它切成若干段每一段都必须是回文串返回所有不同的分割方案。例如 s aab答案是[[a,a,b],[aa,b]]s a答案是[[a]]。字符串长度不超过 16所以哪怕用最暴力的枚举理论上也能在限定时间内跑完。但正因为数据范围小很多人刷完一遍就过去了错过了最有价值的部分——如何把重复计算识别出来并缓存掉。这篇文章就顺着这个思路展开。1. 这道题到底在问什么分割方案的全枚举问题1.1 题目翻译与我第一次的直觉我第一次看到 131 时第一反应是“这不就是找所有切割点吗”。字符串长度为 n中间有 n-1 个可以切的位置每个位置有“切”和“不切”两种状态直观上就是 2^(n-1) 种分割方式。但问题不是简单枚举所有切割组合因为切完以后每一段还得满足“回文串”这个约束。两个条件叠加就成了一个带剪枝的组合枚举问题。用aab举例强制自己手动拆解一次从第 0 位开始尝试第一段。第一段可以取s[0:1] a是回文剩余ab继续分割第一段也可以取s[0:2] aa是回文剩余b继续分割第一段取s[0:3] aab不是回文直接剪掉。这就是一个非常标准的 DFS 决策树每个状态关心“我从哪个位置开始切”然后枚举下一个切割点。树的叶子就是所有合法分割方案。1.2 为什么不能贪心也不能只找最长或最短回文前缀有的人可能会想我先找到最长的回文前缀切掉再递归处理尾巴不就能得到一种方案吗能但题目要的是“所有方案”不是“一种方案”。比如s aaaa最长回文前缀是aaaa按这个策略只能得到[[aaaa]]可实际上还有[[a,a,a,a]]、[[aa,aa]]等多种组合。贪心只能解决“是否存在一种分割”解决不了“枚举全部”。这个特点也决定了这道题不太可能用纯粹的动态规划直接“构造”出所有方案至少不是最直观的写法。动态规划擅长求“数量”“最值”“可行性”而 131 要求的是把每一种方案都原原本本列出来输出规模本身是指数级的所以回溯枚举是更自然的载体。1.3 回溯的经典模子先看最基础的双指针判断回文版本这也是大多数人第一次写出来的版本from typing import List class Solution: def partition(self, s: str) - List[List[str]]: n len(s) res [] path [] def is_palindrome(l: int, r: int) - bool: while l r: if s[l] ! s[r]: return False l 1 r - 1 return True def dfs(start: int) - None: if start n: res.append(path[:]) return for end in range(start, n): if is_palindrome(start, end): path.append(s[start:end 1]) dfs(end 1) path.pop() dfs(0) return res这个写法的骨架非常典型res收集最终答案path记录当前路径dfs(start)表示“正在处理从 start 开始的剩余字符串”。for end in range(start, n)枚举当前要切出的子串终点。当s[start:end1]是回文时把它加入path递归处理end1之后的字符递归返回后再撤销选择。这里有个容易忽略的细节path[:]必须做拷贝。因为path在回溯过程中会被不断修改如果你直接res.append(path)最后res里存的其实是同一个列表对象的引用结果会变成一堆一模一样的空列表。这个坑我见过不少人踩过尤其是刚接触回溯的同学。2. 暴力回溯跑通之后瓶颈卡在哪里2.1 回文判断的重复计算基础版本能通过 LeetCode因为 n 最大才 16。可如果只看“能过”就收手会错过一个很关键的优化点is_palindrome(start, end)这个判断在递归过程中被反复调用而很多区间其实已经被判断过了。举个例子s aab的递归过程里is_palindrome(1, 1)和is_palindrome(2, 2)这种单字符区间会被多个分支共用。单字符还好双指针一眼就看完如果是长字符串比如abcbca里的某个长区间双指针要从两端往中间扫一圈。更关键的是同一个区间可能在完全不同的递归路径下被问一次问完之后结果就丢了下次遇到还得从头扫。我用aaaaaaaaaaaaaaaa做压力测试时体会特别明显。字符串全是a任何一个子串都是回文所以分割方案数等于 2^(n-1)也就是 32768 种方案。每个递归节点都会对每个end调一次is_palindrome双指针哪怕只扫一半累计下来的字符比较次数也多得夸张。虽然 Python 也能扛下来但不舒服。2.2 用最简单的双指针也能过但心里不踏实刷题不能只看能不能 AC还要看代码的扩展价值。131 是纯列举题n 给得小所以双指针版本无所谓。但它的进阶版 132“分割回文串 II”要求的是最少分割次数n 可以到 2000这时候你不可能在每个状态都重新用双指针判断回文必须提前把回文信息预处理出来。换句话说131 的意义在于让你认识“所有方案”类问题的回溯框架而不是让你把双指针判断当成标准答案。如果面试官追问一句“你这里判断回文会不会重复计算”你说“不会因为 n 很小”当然也算一种回答但如果你能直接说出“可以用 cache 把纯函数结果缓存起来”这就是从“能写”到“会优化”的区别。2.3 实测数据与复杂度的直观感受为了看清 cache 的价值我做了个小实验。分别用三个版本跑aaaaaaaaaaaaaaaa双指针回溯、lru_cache 缓存回文判断、DP 预处理回文表。输出结果都一样但耗时差别不小。虽然 LeetCode 上双指针版也能过但观察调用次数更直观双指针版里is_palindrome里层 while 累计执行了很多次字符比较而缓存版本里每个(l, r)区间只会真正计算一次后面全部命中缓存。从复杂度上说回溯枚举所有方案本身是O(n * 2^n)因为方案数量是指数级的每个方案拷贝path需要O(n)。这个指数级是无法通过缓存消除的因为你要输出的东西就有这么多。但判断回文的开销可以优化如果每个区间都用双指针现场扫描相当于额外多了一个n的因子如果把回文判断结果缓存下来判断总成本降到O(n^2)和方案输出成本相比就微不足道了。这就是 cache 缓存的真正价值——它不改变枚举的主框架但把“每个状态里最重的重复劳动”给消掉了。3. cache 缓存为什么要加以及加在哪一层3.1 缓存回文判断细粒度复用先说结论缓存应该加在is_palindrome上而不是加在dfs上。为什么因为is_palindrome(l, r)是一个纯函数只要 s 不变(l, r)确定结果就确定。这种纯函数是最适合缓存的对象。判断一个串是不是回文本质上可以递归定义s[l:r1]是回文当且仅当s[l] s[r]且s[l1:r]也是回文。这个递归定义天然适合用记忆化搜索。当你算过一次is_palindrome(2, 7)之后其他任何递归分支再问同样的区间直接取缓存结果就行不用再比较字符。这就是“cache 缓存”在这道题里的核心作用。用代码表示就是from functools import lru_cache from typing import List class Solution: def partition(self, s: str) - List[List[str]]: n len(s) res [] path [] lru_cache(None) def is_palindrome(l: int, r: int) - bool: if l r: return True return s[l] s[r] and is_palindrome(l 1, r - 1) def dfs(start: int) - None: if start n: res.append(path[:]) return for end in range(start, n): if is_palindrome(start, end): path.append(s[start:end 1]) dfs(end 1) path.pop() dfs(0) return res注意这里is_palindrome的参数是整数下标l和r表示闭区间[l, r]。用lru_cache(None)装饰后所有计算过的(l, r)结果都会被记住。当l r时区间为空或只有一个字符一定是回文这是递归的终止条件。3.2 Python 的 lru_cache 如何使用与注意点lru_cache是 Python 里做记忆化搜索最方便的工具之一但有几个注意点值得单独说。第一被缓存函数的参数必须是可哈希的。整数、字符串、元组都没问题但列表、字典这种可变类型不行。所以判断函数的设计应该接收下标而不是直接接收切片字符串。有人可能会写成is_palindrome(s[l:r1])把子串传进去功能上没错但每次传切片都要创建新字符串反而增加开销而且缓存 key 也变得很长。最优雅的方式就是传(l, r)。第二lru_cache(None)表示缓存不设上限。对于 n ≤ 16 的题目区间总数只有O(n^2)个完全不用担心内存。如果题目 n 很大可能需要考虑缓存大小但至少在这道题里不设限是最简单的。第三不要在类方法上直接装饰一个普通实例方法并依赖self。因为self也会成为缓存 key 的一部分导致缓存无法在多个测试用例之间复用甚至可能内存泄漏。我写题解时通常把is_palindrome定义成partition内部嵌套的函数闭包捕获s这样缓存 key 就只有(l, r)两个整数干净又安全。第四lru_cache本质上就是自顶向下的记忆化搜索它和 DP 预处理不是两种对立方案而是同一思想的不同写法。递归式回文判断里is_palindrome(0, 3)会递归调用is_palindrome(1, 2)这个子问题的结果被缓存后后续任何需要判断s[1:3]的地方都能直接命中。只要理解了这一点你就在两种优化方案之间打通了。3.3 为什么不建议缓存整个 dfs 的返回结果还有一种常见冲动是把dfs(start)的返回值也缓存起来返回“从 start 开始的所有分割方案”。这种思路表面上看很诱人实际上会踩坑。第一如果dfs返回一个列表缓存命中时你会拿到同一个列表对象调用方修改它会造成脏数据。你得返回深拷贝或者改成元组但无论哪种每次构造返回结果的拷贝开销都不小。第二也是最本质的问题这道题要求输出所有方案方案数量本身是指数级的。你就算把dfs(start)的结果缓存下来最后还是要展开所有方案缓存根本不能把指数级的输出规模降下来反而会因为额外存储大量列表导致内存爆炸。所以正确思路是回溯的枚举框架保持不变只把其中“判断回文”这种小而重的重复计算缓存掉。记住一个经验列举类问题里缓存的目标通常是“判断函数”或“子问题的可行性”而不是“整个结果集”。如果题目改成“求分割方案数”那才可以放心缓存dfs(start)的返回值因为计数结果是一个整数重复利用价值极高这也就是 132 题这类问题的思路来源。4. 预备一张回文表DP 预处理的另一种姿势4.1 自底向上的 dp 表怎么填最不容易错除了用lru_cache缓存递归判断另一种常见的做法是先用动态规划预处理出一张回文表再在回溯里直接查表。两种方式殊途同归但 DP 预处理在后续题目里更通用。from typing import List class Solution: def partition(self, s: str) - List[List[str]]: n len(s) dp [[True] * n for _ in range(n)] for i in range(n - 1, -1, -1): for j in range(i 1, n): if j - i 1: dp[i][j] (s[i] s[j]) else: dp[i][j] (s[i] s[j]) and dp[i 1][j - 1] res [] path [] def dfs(start: int) - None: if start n: res.append(path[:]) return for end in range(start, n): if dp[start][end]: path.append(s[start:end 1]) dfs(end 1) path.pop() dfs(0) return res这里dp[i][j]表示s[i:j1]是否为回文。初始化时我把整个表都填成True实际只保证对角线dp[i][i]为True。真正要填的是j i的部分。填表顺序非常关键。dp[i][j]依赖dp[i1][j-1]也就是它的左下角。所以我让i从大到小遍历j从小到大遍历。这样计算dp[i][j]时dp[i1][j-1]已经被算过了。长度 2 的区间要单独处理因为i1 j-1依赖的区间其实是空串不能用同一个递推式所以用j - i 1短路直接比较两个字符是否相等。4.2 lru_cache 与 DP 预处理对比很多初学者会问这两种方案我该写哪种我的回答是看你的目标。如果只是刷 131lru_cache版改动最小在双指针版基础上加几行就完事思路也很直观。如果是为了给 132 或更多字符串题打基础DP 预处理更值得掌握因为后续题目可能要求“任意子串是否回文”被高频访问而 DP 表在填完之后每次查询都是O(1)。对比维度lru_cache 记忆化递归DP 预处理二维表计算方向自顶向下按需计算自底向上全部计算代码改动量小嵌套函数加装饰器即可中等需要先写两层循环查询复杂度缓存命中 O(1)未命中递归计算填表后查询 O(1)空间占用只缓存访问过的区间O(n^2) 全量存储迁移性适合快速优化回溯适合后续动态规划题目其实从底层看两者算出来的是同一张“回文信息表”只是填充的时机不同。lru_cache是懒汉用到哪个区间就算哪个区间DP 预处理是勤快人一次性把n*n的表全部算好。因为 n 很小两种方案在 131 上性能差距不大真正重要的是理解它们的等价性。4.3 验证代码正确性的小技巧写完回溯题我习惯用几组小数据做逻辑验证而不是直接提交。第一组s a答案应该是[[a]]。第二组s aab答案[[a,a,b],[aa,b]]。第三组s aaaa任意分割都合法总共应该有 2^(3) 8 种方案。如果代码输出少于 8 种说明回文判断有误如果输出重复说明path或res的拷贝逻辑出问题。还有一个我自己常用的土办法在dfs里加一个print(start, path)肉眼观察递归顺序是否符合预期。尤其是path.pop()之后路径是否完全回退。回溯题的常见 bug 就是忘记撤销选择导致一个path被多个分支共用最后答案里出现各种奇奇怪怪的组合。如果你用的是 DP 预处理版可以额外验证dp表本身。比如s abbadp[0][3]应该是Truedp[0][2]应该是False。这种小测试能帮你确认两层循环的边界条件写对了没有。5. 从 131 题总结出的刷题迁移思路5.1 看到“所有方案”先想回溯我刷题这么多年对一个规律深信不疑题目里出现“返回所有可能”“列出所有方案”“有多少种分割/组合/排列”的时候第一反应就应该是回溯。回溯的模板非常固定无非是做选择、递归、撤销选择。131 的分割点就是选择93 题复原 IP 地址里的三个点号位置就是选择39 题组合总和里“选当前数字还是要跳到下一个数字”也是选择。回溯题能不能 AC往往不取决于模板本身而取决于你是否能在合适的地方剪枝。131 的剪枝就是“子串必须回文”。如果当前切出来的子串不是回文直接跳过不进入下一层递归。这个剪枝简单但有效能大幅减少无效枚举。5.2 缓存加在哪取决于重复计算长什么样从 131 里最值得带走的不是那段代码而是判断“该不该加 cache”的方法。我总结成三步第一步找递归里的纯函数。所谓纯函数就是输入相同输出必然相同的函数。131 里的is_palindrome(l, r)就是典型代表。第二步看这个纯函数是否会被重复调用。如果不同递归分支会反复问同一个区间就有缓存价值。第三步看缓存的是“小结果”还是“大结果”。判断一个区间是否是回文结果只有一个布尔值缓存起来轻便缓存整个dfs的返回列表结果是一大坨数组容易翻车。这个经验可以迁移到很多题上不同二叉树的重复子树问题、括号生成、单词拆分、戳气球……所有“递归过程中反复计算同一子问题”的场景都值得想一想能不能加 cache。5.3 同类题型与延伸思路131 的延伸题不少我建议按这个顺序刷复原 IP 地址同样是分割字符串只是约束从“回文”变成了“0-255 的数字段”。分割回文串 II从列举所有方案变成求最少分割次数这时不再适合回溯全枚举而是用一维 DP 回文预处理表。单词拆分判断字符串能否被字典中的单词拼接出来经典的记忆化搜索题和 131 的 cache 思想一脉相承。回文子串统计回文子串个数直接用二维 DP 表就能解决。如果你把 131 的回文表优化吃透了刷这些题会顺很多。因为它们本质上都在问同一件事我们能不能快速知道任意子串的性质如果能后面不管是枚举还是计数都站在了稳固的地基上。最后说点个人体会。我刚开始刷 131 的时候也觉得它很简单不就是个 DFS 吗后来被 132 教育了一顿才意识到回文表的预处理有多重要。所以现在看到 131我会刻意把三种写法都写一遍双指针版帮你理解回溯框架lru_cache 版让你体会纯函数缓存DP 预处理版为后续打基础。三道题的时间换来的是一整套字符串分割问题的解题手感这笔账怎么算都值。