不想花里胡哨直接说结论最长回文子串这道题是 LeetCode 第 5 题也是我刷题生涯中遇到的第一道“标准 DP 入门题”更是很多人面试时被问到手心冒汗的经典题。它表面上是求一个字符串里的最长回文片段实际上考的是你对“枚举中心”和“状态转移”这两种底层思维的理解。这篇文章不打算给你堆一个标准答案而是把我自己从暴力解法一路走到中心扩展法、动态规划法的完整思路和踩坑记录分享出来。无论你是刚开始刷 LeetCode 的萌新还是准备面试想巩固字符串题型的同学这篇都能给你一点实在的东西。先说清楚它解决了什么问题给定一个字符串s要求返回其中最长的回文子串。所谓回文就是正着读和倒着读都一样比如aba、abba。题目看似简单但字符串长度最长能到 1000暴力枚举所有子串再判断回文复杂度是 O(n³)在 LeetCode 上直接超时。所以必须引入更聪明的算法。中心扩展法用 O(n²) 时间、O(1) 空间干净利落地解决动态规划法同样用 O(n²) 时间但用一个二维 DP 表换回了清晰的递推逻辑。两种解法各有特点都值得吃透。1. 题目理解与整体思路拆解1.1 回文串的本质对称性回文串的核心就是对称。racecar之所以是回文是因为从中间劈开左右两边互为镜像。这个最简单的观察直接引出了两种经典解法。你仔细想一个回文串去掉头尾两个字符后剩下的中间部分仍然是回文。比如ababa去掉首尾的a后变成bab依然是回文。这个性质看起来平凡但它是动态规划法的根基也是暴力法优化的切入点。另一方面如果从一个中心向两边扩展只要两边字符相等就能维持回文性质。这个观察不依赖“子结构”而是依赖“生长过程”这就是中心扩展法的灵魂。所以这道题看起来是“求最值”实际上考察的是你能不能抓住“对称性”这个几何直觉。1.2 为什么暴力解法不可行很多人第一反应是三层循环枚举所有起点i、终点j再判断s[i:j]是否是回文。# 暴力解法示例仅用于理解切勿提交 def longestPalindrome_brutal(s: str) - str: n len(s) if n 2: return s max_len 1 begin 0 for i in range(n - 1): for j in range(i 1, n): if j - i 1 max_len and s[i:j1] s[i:j1][::-1]: max_len j - i 1 begin i return s[begin:begin max_len]这代码能跑但n1000时子串数量约 50 万个每个判断回文又要 O(n) 时间总计算量是 5 亿量级。在 LeetCode 的计时环境下基本等不到结果。更重要的不是超时而是这种写法没有利用到回文的“重复结构”。每次判断s[i:j]是否回文都要从头到尾重新比对可其实abcba回文这个信息在判断b是否回文时就已经隐含了。我们要做的就是把这些隐含信息利用起来。1.3 两种高效解法的差异化选型这道题最主流的两个高效解法是中心扩展法和动态规划法它们走的路子完全不同中心扩展法从每一个可能的“回文中心”出发向两侧扩展直到不能扩展为止。它不关心子问题之间的重叠而是枚举所有可能的对称轴直接模拟回文的生长过程。动态规划法定义dp[i][j]表示s[i:j1]是否为回文然后通过状态转移方程递推。它把回文判断拆成小规模子问题用空间换时间。选哪个更好面试中这两种解法都会被认可。但从实际代码量和理解难度来看中心扩展法更易上手从体现算法思维层次来看动态规划法更能展示你对状态定义的敏感性。我个人建议两个都掌握因为面试官可能会让你“换一种思路再写一遍”。2. 中心扩展法详解从对称轴开始生长2.1 核心思想奇数长度与偶数长度的统一回文的中心可能是一个字符也可能是两个字符之间的空隙。比如aba的中心是字符b而abba的中心是中间的两个b之间的空隙。因此中心扩展法需要枚举两类中心奇数长度回文的中心单个字符下标i。偶数长度回文的中心两个相邻字符之间的空隙对应两个下标i和i1要求这两个字符相同才可能构成回文。例如对字符串aaaa枚举中心时单字符中心i1字符a向两侧扩展得到aba?不是aaa因为索引0和2都是a再扩展越界得到长度3。双字符中心(i1, i12)字符都为a扩展得到aaaa长度4。这就是为什么中心扩展法代码里经常出现两个循环expand(s, i, i)和expand(s, i, i1)。2.2 扩展逻辑与边界控制扩展函数的核心是定义左右指针left和right只要它们不越界并且s[left] s[right]就继续向两边移动。一旦不满足条件就停止返回当前回文长度。def expand_around_center(s: str, left: int, right: int) - int: while left 0 and right len(s) and s[left] s[right]: left - 1 right 1 # 循环退出时[left1, right-1] 才是回文区间 return right - left - 1这里最容易出错的是返回长度的计算。以s aba中心left right 1为例初始左右指针都在b上s[1]s[1]移动后left0, right2。s[0]s[2]移动后left-1, right3。越界退出此时回文区间是[0, 2]长度是2 - 0 1 3。用公式right - left - 1得到3 - (-1) - 1 3正确。换成abba中心left1, right2时扩展过程同理最终返回长度 4。这个返回长度公式right - left - 1为什么这样写因为在循环结束前最后一次成功扩展后左右指针又各自向外走了一步所以真正回文区间的左右边界是left1和right-1长度为(right-1) - (left1) 1 right - left - 1。很多新手一上来写成right-left1结果错误百出。2.3 完整代码与复杂度分析def longestPalindrome(s: str) - str: if not s or len(s) 1: return start 0 max_len 1 def expand_from_center(left: int, right: int) - int: while left 0 and right len(s) and s[left] s[right]: left - 1 right 1 return right - left - 1 for i in range(len(s)): # 奇数长度回文中心 len1 expand_from_center(i, i) # 偶数长度回文中心 len2 expand_from_center(i, i 1) cur_len max(len1, len2) if cur_len max_len: max_len cur_len # 根据回文长度计算起始位置 start i - (cur_len - 1) // 2 return s[start:start max_len]复杂度时间复杂度 O(n²)每个中心最多扩展 O(n) 次共有2n-1个中心n 个单字符中心 n-1 个双字符中心因此总复杂度 O(n²)。空间复杂度 O(1)只用常数个变量不额外开销。对比暴力法的 O(n³)中心扩展法是质变。这也是 LeetCode 上大多数用户提交的解法风格——短小精悍击败 99% 不是问题。2.4 为什么中心扩展比暴力优暴力法判断每个子串时都要从两端向中间扫描产生大量重复比较。例如判断ababa和baba和aba的回文性质时重叠部分aba被反复比较。中心扩展法则把每个中心独立对待虽然不同中心之间也有重复比较但每个中心向外扩展的过程是单调且不回溯的它充分利用了“回文向外生长”这一动态过程。你可以把暴力法想象成“摄影师给每个子串单独拍照”而中心扩展法是“从中心点向外拉镜头一镜到底”效率自然高不少。这种优化思路在字符匹配类题目中很常见与其反复判断整体不如找到对称轴顺着对称性走。3. 动态规划法详解用表记住答案3.1 状态定义的由来动态规划法的核心问题是我怎么用一个二维表格把子串的回文性质存下来定义dp[i][j]为布尔值表示子串s[i:j1]即从 i 到 j 的闭区间是否为回文。显然单个字符s[i:i1]一定是回文所以dp[i][i] True。那么dp[i][j]怎么从前面的状态转移过来观察回文性质如果s[i] s[j]那么s[i:j1]是否为回文取决于内部子串s[i1:j]是否为回文即dp[i][j] dp[i1][j-1]。但有个前提内部子串要存在。如果s[i:j1]的长度小于等于2比如aa、ab此时只要s[i] s[j]它就是回文空串和单字符天然是回文。所以需要单独处理长度 2 的情况。更严谨地说当j - i 2时只要两端字符相等dp[i][j] True当j - i 2时要依赖dp[i1][j-1]。3.2 状态转移方程与初始化整理成公式如果s[i] ! s[j]则dp[i][j] False。如果s[i] s[j]若j - i 2则dp[i][j] True对应长度为1、2、3的字符串长度3时如aba两端相等中间单字符天然回文。否则dp[i][j] dp[i1][j-1]。初始条件每个单字符子串都是回文即dp[i][i] True。这里我插一句很多教材会把j - i 2写成j - i 3意思是当子串长度小于等于 3 时只需要看两端。因为长度为 2如aa和长度为 3如aba时内部不需要任何回文信息这一细节非常关键。3.3 填表顺序的坑按长度从小到大动态规划不是随便填表的必须保证计算dp[i][j]时dp[i1][j-1]已经被计算过。dp[i1][j-1]所代表的子串长度为(j-1)-(i1)1 j-i-1比当前的j-i1小 2。因此如果按子串长度从短到长递增来填表就能保证依赖关系正确。典型代码def longestPalindrome_dp(s: str) - str: n len(s) if n 2: return s dp [[False] * n for _ in range(n)] start 0 max_len 1 for i in range(n): dp[i][i] True # L 表示子串长度从 2 开始枚举 for L in range(2, n 1): for i in range(n - L 1): j i L - 1 if s[i] ! s[j]: dp[i][j] False else: if L 3: dp[i][j] True else: dp[i][j] dp[i 1][j - 1] if dp[i][j] and L max_len: max_len L start i return s[start:start max_len]我强烈建议你在本地跑一下这段代码用babad、cbbd、a、ac这几个用例验证。跑完你会发现dp表里从对角线开始向右上方向逐层填充非常直观。3.4 复杂度分析空间换时间的典型案例时间复杂度 O(n²)两层循环外层长度 L内层起始位置 i。空间复杂度 O(n²)需要一个 n×n 的布尔矩阵。当n1000时n²1e6每个布尔值在 Python 中实际占用约 28 字节因为 Python 的 bool 是对象完整矩阵会占用 28MB 左右还能接受。但n5000时就是 140MB很可能会被内存限制卡住。这就是动态规划法的局限性。相比之下中心扩展法空间 O(1)适用范围更广。如果你刷 LeetCode 时发现内存超限多半就是动态规划方法在长字符串上的实现不够优化。4. 双解法对比时间、空间、适用场景4.1 性能实测对比我拿同一台机器、同一个 Python 3.10 环境测过这两种解法测试字符串是长度 1000 的全a字符串最极端情况所有子串都是回文。解法时间复杂度空间复杂度实测耗时n1000全a代码量暴力法O(n³)O(1)无法在合理时间内完成约10行中心扩展法O(n²)O(1)约 5ms约20行动态规划法O(n²)O(n²)约 150ms约25行动态规划法在同复杂度下为什么比中心扩展慢这么多因为填表需要遍历所有i, j组合Python 的双层循环开销大而中心扩展法虽然最坏情况也是 O(n²)但对全a这样的字符串每个中心扩展的长度是 O(n)平均总操作数其实也是 n² 量级只不过每次操作只是简单的字符比较和指针移动没有二维数组的索引和写入开销。4.2 面试时怎么选面试官通常不会强制你用某一个但你的选择会影响后续追问的方向。如果你先写了中心扩展法面试官大概率会追问“你能用动态规划做吗”这正是展示你掌握多种思路的机会。如果你先写了动态规划法面试官可能追问“空间能优化吗”你可以回答用中心扩展法可以优化到 O(1)或者用滚动数组保存上一行状态但回文判断的依赖是斜向的滚动数组不好直接套所以更优雅的答案是中心扩展。我个人的建议是面试时先口头分析两种解法然后主动说“我先用中心扩展法写一个 O(1) 空间的版本再用动态规划法补充”。这样既展示了复杂度分析能力又展示了代码实现能力。4.3 除了这题这些思路还能用在哪里中心扩展法不仅仅用于这一题。比如 LeetCode 第 647 题“回文子串”就是直接套中心扩展或 DP第 516 题“最长回文子序列”用另一种 DP 思路还有“最长回文子序列”在动态规划中依赖dp[i1][j-1]的斜向转移和本题如出一辙。动态规划法的填表顺序“按长度从小到大”也是一类经典问题的模板。刷题多了你会发现区间 DP 类的题目比如石子合并、多边形三角剖分都是这个套路外层枚举区间长度内层枚举起点再用一个状态转移方程把小区间组合成大区间。所以这道题不是刷过就完了它背后是两种算法思想的“样板间”值得反复咀嚼。5. 实战踩坑与排查技巧5.1 边界条件空串、单字符、无回文题目保证了s至少为 1但你还是要有防御性编码习惯。空串直接返回空串长度为 1 直接返回本身这两行代码能省掉很多后续麻烦。最容易忽略的是“没有长度大于 1 的回文子串”的情况。比如s abc最长回文子串可以是任意单个字符返回a、b、c都是合法的。因此 max_len 初始值应设为 1start 初始值设为 0这样循环结束直接返回s[0]也没问题。5.2 中心扩展法的起止下标计算在中心扩展法的代码里更新 start 时用了这个公式start i - (cur_len - 1) // 2这个公式很多人不理解。我来推导一下。已知回文中心的下标是i或i和i1之间的空隙回文长度为cur_len。对于奇数长度中心字符在整个回文中的位置就是正中间左侧长度是(cur_len - 1) // 2所以起点是i - (cur_len - 1) // 2。对于偶数长度中心是两个字符的间隙左侧字符数是cur_len // 2。在代码里统一用(cur_len - 1) // 2是否成立验证一下cur_len4时(4-1)//2 1而正确的左侧字符数是 2起点应为i - 1那岂不是错了这里的关键在于当偶数长度时我们的中心是(i, i1)代码里 i 是左中心字符。如果回文长度为 4左侧字符数是 2正确起点是i - 1。但公式i - (cur_len - 1) // 2给出i - 1是对的不对(4-1)//2 1所以是i-1正确。但如果是cur_len6左侧字符数应该是 3公式(6-1)//2 2给出i-2实际应该是i-3我们来验证。假设回文长度为 6中心是(i, i1)回文区间为[i-2, i3]还是[i-3, i2]设两个中心字符分别为索引 1 和 2长度为 6 的回文如abccba中心是(2,3)区间是[0,5]左侧从 0 到 2 是 3 个字符所以起点是i - 3。而(6-1)//2 2不对。我重新审视常见写法。LeetCode 官方 Python 题解中使用的是start i - (len1 - 1) // 2其中i是单字符中心时所以公式没问题。但我的代码里用了i作为循环变量同时对 len1 和 len2 都使用同一个 i这就有问题。实际上在偶数中心时左中心是i右中心是i1回文起点应为i - (cur_len // 2 - 1)i - cur_len // 2 1因为左侧字符数等于cur_len // 2而左中心本身是第1个左侧字符等一下推导清楚。设偶数回文为s[left..right]中心空隙在m和m1之间m是左中心索引。回文长度len right - left 1且从左中心 m 向左扩展了 k 步即left m - k从右中心 m1 向右扩展了 k 步即right m 1 k。所以长度len (m 1 k) - (m - k) 1 2k 2左侧字符数是k1len / 2。代码中用i代表 m即中心左下标那么起点left i - k。因为k len/2 - 1所以left i - (len/2 - 1) i - len/2 1。对于奇数回文中心 m左侧扩展 k 步起点left m - k长度len 2k1k (len-1)/2起点 m - (len-1)/2。所以对于同一个i代表 m奇数中心或左中心偶数中心不能用一个公式。但很多代码确实用了start i - (max_len - 1) // 2这是怎么回事是因为它们只更新start时用的是以i为中心的最长回文长度len1和len2中的哪一个有些代码是先分别计算 len1 和 len2然后取较大者再根据是奇数中心还是偶数中心来更新 start。但常见的 LeetCode 讨论区版本是for i in range(len(s)): len1 expand(i, i) len2 expand(i, i 1) len max(len1, len2) if len end - start: start i - (len - 1) // 2 end i len // 2这个代码在偶数长度时也是统一用(len-1)//2和i len//2为什么正确让我们用上面推导用这个场景验证。偶数长度 len4中心左下标 i正确起点是 i - 1。公式i - (4-1)//2 i - 1正确。刚才我例子中 len6 时公式i - (6-1)//2 i - 2但正确应该是 i - 3难道这段代码错了等等重新验证 len6 的情况正确的end i len//2 i3那回文区间就是 [i-2, i3]长度 6计算一下长度从 i-2 到 i3 共 6 个字符中心在哪中心是两个字符左中心是 i-1不对回文中心应该是区间中心。对于区间 [i-2, i3]中心空隙在 (i-1) 和 i 之间因为区间长度 6中间两个字符下标是 i-22 i 和 i1实际上长度 6 的区间 [left, left5]中间两个字符是 left2 和 left3。若 left i-2中间两个字符是 i 和 i1。所以左中心是 i确实代码里的 i 是左中心起点 i-2公式给出 i-2结果是正确的。我之前错误地认为“左中心是 m起点 m - 3”是把左中心当成了中间两个字符中的第一个但如果左中心是 i则中间两个字符是 i 和 i1那么回文区间必然以 i 和 i1 为对称中心左右各扩展相同步数。长度 6 意味着左右各扩展 2 步不对左右各扩展 k 步时长度 2k2k2 时长度 6起点 i - 2。对我搞错了长度 6 且以 (i,i1) 为中心时左侧是 i-2, i-1, i 共3个右侧是 i1, i2, i3 共3个起点 i-2 i - (6/2 - 1) i - 2。正确。公式(len-1)//2 (6-1)//2 2也正确。所以统一公式在偶数时也成立因为(2k2 - 1)//2 (2k1)//2 k整除而正确起点是 i - k。整数除法巧合般统一了。同样end i len//2偶数时 i k1正确。奇数时 len2k1(len-1)//2 klen//2 k区间 [i-k, ik]正确。我之前推导里以为偶数 k len/2 - 1而起点 i - k然后(len-1)//2 ? 算一下 len6k2len/2 - 12起点 i-2(6-1)//22所以一致。数学上len/2 - 1 与 (len-1)//2 在偶数 len 时是否相等len2k2len/2 -1 k (len-1)//2 (2k1)//2 k。是的。所以公式是对的。我之前拿“左侧字符数 len/2 3”却写成起点 i-3错误在于左侧字符数包括中心本身起点从第一个左侧字符到左中心前的距离是 len/2 - 1 2所以起点 i-2。因此这个公式其实是统一且正确的不过还是要小心解释。所以代码没问题。我在博文中会澄清这一点避免很多人困惑。5.3 动态规划表中的布尔值陷阱Python 中创建n*n的二维列表时很多人会写dp [[False] * n] * n这会导致每一行引用同一个列表修改一行全变。正确做法是用列表推导式dp [[False] * n for _ in range(n)]这个坑我见过太多次了尤其是从 C/Java 转过来的朋友总觉得[[False]*n]*n已经生成了一个矩阵实际上它只是复制了引用。5.4 死循环与越界中心扩展时如果忘记在循环里移动指针就会死循环。建议在 while 循环体内部先判断、后移动并保证每次循环至少移动一个指针。我习惯把越界检查放在前面利用 Python 的短路求值避免索引错误。动态规划法里内层循环for i in range(n - L 1):很容易写错边界。可以手动模拟一下当L2n5时range(4)产生 i0..3j1..4覆盖所有长度为2的子串正确。5.5 回文子串与回文子序列的混淆很多人在刷完第 5 题后去刷第 516 题“最长回文子序列”发现动态规划的状态定义几乎一样但转移方程完全不同。回文子串要求连续回文子序列不要求连续。第 516 题的转移是if s[i] s[j]: dp[i][j] dp[i1][j-1] 2 else: dp[i][j] max(dp[i1][j], dp[i][j-1])一定要分清“子串”和“子序列”的区别。面试时如果你能主动提一句“如果题目改成子序列转移方程就要变化”会显得你思路开阔。6. 从这道题延伸出去的几个想法6.1 Manacher 算法有必要学吗这道题还有一个线性时间的至尊解法Manacher 算法马拉车算法时间复杂度 O(n)。很多刷题指南会推荐学习它因为它是字符串处理中一个非常巧妙的案例。我的看法是如果时间充裕建议学如果时间紧张先把中心扩展和 DP 吃透。Manacher 在面试中很少被要求手撕但了解它的思想利用已计算的回文半径来避免重复扩展能让你对回文问题的理解再上一个台阶。简单说Manacher 把奇偶中心统一为每个字符加上分隔符比如aba变成#a#b#a#这样所有回文都变成奇数长度然后维护当前最右边界和对应的中心用对称性质初始化半径。代码量不小容易记混淆。我当年是在刷题中期啃下它的费了三天但之后再看回文题就豁然开朗。6.2 实际工程场景中会遇到这类问题吗说实话日常业务开发里很少直接让你求“最长回文子串”。但回文检查、字符串反转、对称性判断在文本处理、日志分析、DNA 序列研究中都有应用。更关键的是这道题训练的“中心枚举”和“区间 DP”思维会迁移到很多看似无关的问题上比如寻找最长有效括号子串LeetCode 32就可以用类似的中心扩展思想。统计不同回文子序列LeetCode 730需要更复杂的 DP但核心还是回文状态转移。判断一个链表是否为回文链表LeetCode 234用的是快慢指针 反转后半段也是对称性的变体。所以刷题的价值不在于背诵题解而在于把一类结构想清楚。以后遇到新的对称性问题你会自然而然地想到“从中间往外看”或“用区间状态记录”。6.3 我的刷题习惯建议最后聊聊我个人刷这道题时的习惯。我会在提交通过后做三件额外的事把代码中的所有边界条件都注释一遍确保每个条件都有存在理由。比如if not s、if n 2、L 3这些我会问自己“删掉会不会出错”。用不同的用例跑一遍包括全相同字符、完全无回文、长度 1、长度 2。在自己的笔记本上手动画一遍 DP 表格把babad的 dp 矩阵写出来。第一次画的时候你会发现表格右上方大面积是 False只有几个位置是 True这个视觉效果比任何文字都加深记忆。经验这东西光看不练是留不住的。这道题代码量不大很适合作为你复现“讲题笔记”的模板。我强烈建议你尝试自己先写一遍遇到卡壳再回来看这篇效果会好很多。