最长回文子串LeetCode第5题刷过一阵子算法题的人大概率都在这道题上花过时间。题目本身一句话就能说清楚给你一个字符串找出其中最长的回文子串。所谓回文就是正着读和倒着读都一样比如aba、bb、a。但就是这么个看似简单的问题从暴力解到线性解中间隔了好几个层级几乎把字符串处理的核心技巧都串起来了。这篇文章我打算把这道题从头到尾拆一遍包含四类主流解法暴力枚举、中心扩展、动态规划、Manacher算法。无论你是刚开始刷题的新手还是准备面试想快速回顾最优解的选手应该都能在这里面找到自己需要的那一层。我会把每一类解法的思路、代码、复杂度、适用场景以及我实际写代码时踩过的坑都讲清楚。1. 先读懂题目回文到底在考什么1.1 题目表达与边界条件LeetCode第5题的原题描述很简单给定一个字符串 s找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例一输入 babad输出是 bab 或者 aba 都算正确因为题目只要最长回文子串不要求唯一。示例二输入 cbbd输出是 bb。这里有几个细节容易被忽略。第一单个字符本身也是回文长度是1。第二空字符串要单独处理这在工程代码里是理所当然的但在刷题时经常会被忘记。第三回文分两种形态奇数长度的回文中心是一个字符比如 aba 的中心是 b偶数长度的回文中心是两个字符之间的间隙比如 bb 的中心是 b 和 b 之间那个空位。这两种形态在后面的中心扩展法里就会体现出来如果只考虑其中一种测试用例一跑就露馅。1.2 暴力解法为什么不行最直观的思路是枚举所有子串判断每个子串是否是回文然后记录最长的那个。判断一个子串是不是回文需要从两端向中间逐个比较字符这个复杂度是 O(L) 的L 是子串长度。枚举所有子串的复杂度是 O(n^2)乘上判断的 O(n)整体复杂度是 O(n^3)。当 n1000 时最坏情况下大约要执行 10 亿次字符比较实际跑起来会明显卡顿在LeetCode上基本会超时。不过别急着否定暴力解法它在两个场景下仍然有价值一是作为写代码前的思路热身帮自己确认边界条件二是当 n 很小比如长度不超过100时暴力解法是维护成本最低的做法不容易出bug。我见过很多人一上来就背 Manacher 模板结果忘了暴力怎么写。真到面试时面试官问你如果字符串很短你会怎么处理你反而要花时间去想最朴素的方案这就尴尬了。所以暴力解法虽然不推荐用于提交但思路还是建议理解一下。public String longestPalindrome(String s) { if (s null || s.length() 1) { return ; } int n s.length(); String result ; for (int i 0; i n; i) { for (int j i; j n; j) { if (isPalindrome(s, i, j) (j - i 1) result.length()) { result s.substring(i, j 1); } } } return result; } private boolean isPalindrome(String s, int left, int right) { while (left right) { if (s.charAt(left) ! s.charAt(right)) { return false; } left; right--; } return true; }这段代码放在这里主要是帮助理解题目语义以及后续优化到底优化掉了什么。暴力解法重复做了大量无效判断比如子串 abcba 在判断它整体是回文时其实已经知道 bcb 是回文但这个信息没有被复用导致同一个字符被反复比较。后面几种解法本质上就是在想办法减少这种重复劳动。2. 中心扩展法面试中最值得先写出来的解2.1 思路从中心往两边“对掌”回文天然具有中心对称的结构。与其枚举左右边界再去判断不如换个方向思考我把每个位置当成回文的中心然后向左右两边同时扩展只要左右字符一致就继续扩直到扩不动为止这样得到的最大扩展范围就是一个回文子串。这里必须处理一件事回文中心可能是字符也可能是字符间隙。所以对每个位置 i要做两类扩展以 s[i] 为奇数长度回文的中心比较 s[i-1] 和 s[i1]以 s[i] 与 s[i1] 之间的间隙为偶数长度回文的中心比较 s[i] 和 s[i1]。如果漏掉第二类比如测试用例 cbbd中心扩展只会找到长度为1的 c 或 d不会得到正确答案 bb。这个方法的复杂度是 O(n^2)。表面上看每个中心向外扩展最多 O(n) 次乘上 n 个中心就是 O(n^2)。但实际扩展时大多数情况很快就停下来了所以常数很小。对于 n1000 的题设完全没问题这也是我面试时优先推荐它的原因思路简单代码短不容易在紧凑的时间内心态崩掉。2.2 代码实现与易错点public String longestPalindrome(String s) { if (s null || s.length() 1) { return ; } int start 0; int maxLen 1; for (int i 0; i s.length(); i) { int len1 expandAroundCenter(s, i, i); int len2 expandAroundCenter(s, i, i 1); int len Math.max(len1, len2); if (len maxLen) { maxLen len; start i - (len - 1) / 2; } } return s.substring(start, start maxLen); } private int expandAroundCenter(String s, int left, int right) { while (left 0 right s.length() s.charAt(left) s.charAt(right)) { left--; right; } return right - left - 1; }几个我实际写的时候容易出问题的地方第一start 的计算。如果当前最长回文长度是 len中心下标是 i那么起始位置是 i - (len - 1) / 2而不是 i - len / 2。原因在于偶数长度回文时中心是两个字符之间的位置用整数下标 i 和 i1 表示中心间隙时起始位置需要做偏移处理。我建议把它和 len1、len2 分开看不要混在一起算否则很容易多偏移一位。第二expandAroundCenter 返回的长度是 right - left - 1。因为循环退出时 left 和 right 已经向两边多走了一步回文区间是 [left1, right-1]长度就是 right - left - 1。这是这块代码最经典的边界写错了会导致结果差两。第三substring 是左闭右开区间。返回时用 s.substring(start, start maxLen)右边界是 start maxLen不是 start maxLen - 1。这个在Java里太容易出错了报错信息还是 StringIndexOutOfBoundsException很多人第一反应是数组下标问题其实是区间算错了。中心扩展法在工程里的优势也很明显它不需要额外空间不像动态规划要开一个 O(n^2) 的二维数组。如果字符串长度不超过几千我一般都会优先写这个方案。3. 动态规划把“已验证”的结果存下来3.1 状态定义与转移方程动态规划的思路和中心扩展刚好互补。中心扩展是从小到大扩大范围动态规划则是把子问题的结果存起来自底向上推导。用 dp[i][j] 表示子串 s[i..j] 是否为回文true 表示是false 表示不是。状态转移方程是这样的dp[i][j] (s[i] s[j]) (j - i 3 || dp[i 1][j - 1])这个方程要拆开来理解。一个子串是回文必须同时满足两个条件首尾字符相等去掉首尾后剩下的子串也是回文。但这里有个特例当子串长度小于等于3时只要首尾相等中间部分无论长度是0还是1天然就是回文。所以 j - i 3 这个条件要先判断避免出现 dp[i 1][j - 1] 中 i1 j-1 这种不合法的情况。这个方程其实就是对回文结构做了最直接的建模后面 Manacher 能在线性时间完成就是利用了更隐蔽的回文对称性。但从可理解性来说动态规划是最贴近数学归纳法的方案。3.2 遍历顺序是这道题最容易踩的坑二维动态规划对遍历顺序非常敏感。因为 dp[i][j] 依赖的是 dp[i1][j-1]也就是左边界更靠右、右边界更靠左的一个更短的子串。如果按照 i 从0到n、j 从 i 到 n 的顺序去填表你会发现计算 dp[i][j] 时dp[i1][j-1] 可能还没被算出来拿到的就是默认值 false导致结果出错。正确做法是按子串长度从短到长遍历。先算所有长度为1的其实长度为1必然是回文可以初始化成 true再算长度为2的、长度为3的以此类推。这样在算长度为 len 的子串时长度为 len - 2 的子串一定已经填好表了可以直接取用。public String longestPalindrome(String s) { if (s null || s.length() 1) { return ; } int n s.length(); boolean[][] dp new boolean[n][n]; int start 0; int maxLen 1; for (int i 0; i n; i) { dp[i][i] true; } for (int len 2; len n; len) { for (int i 0; i n - len; i) { int j i len - 1; if (s.charAt(i) s.charAt(j)) { if (len 2 || dp[i 1][j - 1]) { dp[i][j] true; if (len maxLen) { maxLen len; start i; } } } } } return s.substring(start, start maxLen); }这里有个细节值得多说一句为什么长度为2的也要单独判断因为当 len 2 时子串只有两个字符此时 dp[i1][j-1] 对应的是 dp[i1][i]下标是 i1 i这个位置在数组里的默认值是 false但它不代表“中间部分不是回文”而是“中间部分根本不存在”。所以 len 2 时只要首尾相等直接判定为回文。动态规划的时间复杂度是 O(n^2)空间复杂度也是 O(n^2)。n1000 时boolean 数组大约是 100 万字节在Java里 boolean 数组每个元素占1字节内存占用大概在 1MB 左右完全在可接受范围。但如果 n 变成 10 万这个方法就会因为内存问题直接不可用。这也是为什么后续还要学 Manacher。4. Manacher算法线性时间的答案4.1 预处理把奇偶问题统一掉Manacher算法之所以能做到 O(n)核心思想是“利用已经计算过的回文半径信息减少重复比对”。但在此之前它先解决了一个结构上的麻烦奇偶回文中心形态不同。解决办法是往字符串每个字符之间和首尾插入一个特殊字符比如 #这样原串 aba 会变成 #a#b#a#原串 bb 会变成 #b#b#这里我简化展示实际代码还会加哨兵字符。插入之后任何回文都变成了奇数长度因为现在每个回文都有一个明确的中心字符要么是原始字符要么是 #。这个预处理让后面所有的中心扩展都只需要处理一种情况逻辑大大简化。我在预处理时还会额外在开头加 ^、在结尾加 $作用有两个一是作为 while 循环的边界避免每次判断下标越界二是这两个字符在比较时永远不会相等可以保证扩展过程在耗尽字符串之前先停下。不过这也带来一个隐患如果原字符串本身包含 ^ 或 $哨兵就失效了。后面我会单独讲这个坑。4.2 核心变量center 与 rightBound先定义几个数组和变量。p[i] 表示以预处理字符串 t[i] 为中心的回文半径扩展步数注意这里半径不含中心本身。也就是说如果 t[i] 能向外扩展 k 步那这个回文在原串中对应的长度就是 k。这个定义是网上很多模板写法的差异来源看题解时一定要先确认作者对 p[i] 的定义否则照着抄很容易错。另外维护两个关键变量center 表示当前已知回文的中心下标rightBound 表示这个回文的右边界下标。它们描述的是一个“已经探索过的最右回文区间”。处理新位置 i 时如果 i 在 rightBound 左边说明 i 处于一个已知回文区间内那么一定可以找到 i 关于 center 的对称位置 mirror。利用回文的对称性p[i] 至少可以取 p[mirror]但不能超过 rightBound - i所以初始化是p[i] Math.min(rightBound - i, p[mirror])如果 i 在 rightBound 右边或等于 rightBound说明前面没有任何信息可以借用只能老老实实从0开始扩展。这个“借信息”的动作就是 Manacher 比中心扩展快的原因。每个字符最多被扩展失败一次所以总的时间复杂度是线性的。4.3 完整代码与手推验证public String longestPalindrome(String s) { if (s null || s.length() 1) { return ; } String t preProcess(s); int n t.length(); int[] p new int[n]; int center 0; int rightBound 0; int maxLen 0; int centerIdx 0; for (int i 1; i n - 1; i) { int mirror 2 * center - i; if (i rightBound) { p[i] Math.min(rightBound - i, p[mirror]); } else { p[i] 0; } while (t.charAt(i 1 p[i]) t.charAt(i - 1 - p[i])) { p[i]; } if (i p[i] rightBound) { center i; rightBound i p[i]; } if (p[i] maxLen) { maxLen p[i]; centerIdx i; } } int start (centerIdx - maxLen) / 2; return s.substring(start, start maxLen); } private String preProcess(String s) { StringBuilder sb new StringBuilder(^); for (char c : s.toCharArray()) { sb.append(#).append(c); } sb.append(#$); return sb.toString(); }这版代码里 p[i] 表示扩展步数maxLen 就是最终答案的长度。start 的计算公式是 (centerIdx - maxLen) / 2这个式子看着奇怪其实是预处理字符串索引和原字符串索引之间的换算关系。我建议你拿一个具体例子手推一遍比如 babad预处理后 t ^#b#a#b#a#d#$最长回文中心是中间的 b下标是 6p[6] 3maxLen 3start (6 - 3) / 2 1s.substring(1, 4) 就是 aba完全正确。这种偏移换算关系在考试和面试时经常让人紧张出错我的建议是不要死记公式而是根据 p[i] 的定义现场推导一遍。推过一遍之后就会明白delete预处理字符串里开头的哨兵占了一个位置所以原串索引和预处理串索引之间不是简单的倍数关系而是存在一个偏移为1的线性关系。4.4 为什么它真的是线性时间很多人看 Manacher 觉得像是玄学但其实复杂度分析有严格依据。最关键的观察是rightBound 在整个算法过程中只向右移动从不回退。每次 while 循环成功扩展都会让 rightBound 变长而 i 从 0 扫到 n每个位置只会被处理一次。即使 p[i] 被借用了对称点信息后续扩展最多扩展到 rightBound 位置一旦扩展越过 rightBoundrightBound 就更新到更远的位置。所以 while 循环的总执行次数是 O(n) 的再加上外层 for 循环 O(n)整体复杂度就是 O(n)。这也是它能在超长字符串下依然保持快速的原因。5. 几种解法怎么选5.1 复杂度与适用场景对比把四种解法列在一起看差距非常直观解法时间复杂度空间复杂度适合场景暴力枚举O(n^3)O(1)仅用于理解题意中心扩展O(n^2)O(1)面试手写性价比最高动态规划O(n^2)O(n^2)适合回文计数等衍生题ManacherO(n)O(n)竞赛、超长字符串场景这里的复杂度只针对 n 是字符串长度的情况。如果 n 在1000左右中心扩展和动态规划都能在几毫秒内跑完选哪个更多是看题目延伸方向。如果面试官问的是有多少个回文子串动态规划的状态定义可以比较自然地进行计数如果问的是最长回文子串是否存在某种扩展变体中心扩展更容易现场改代码如果 n 到了 10^5 甚至更大Manacher 就是不二之选了。5.2 我实际刷题时的策略我自己的刷题策略是第一遍先只写中心扩展因为它代码最短、最不容易出错跑通过就能加深对回文结构的理解。第二遍再用动态规划完全重写训练自己处理遍历顺序这类细节。最后才是把 Manacher 当成进阶内容去专项练习不急着背模板而是反复手推代码直到能不卡壳地从头写出来。面试场景和刷题场景还不一样。面试官通常更看重思路的递进过程。你可以先讲清楚暴力解的问题然后提出中心扩展分析复杂度已经明显优化。如果面试官问“还能不能再快”再引出 Manacher这时候你会很自然地讲到回文的对称性复用整个逻辑链条是完整的。反过来如果你一上来就甩 Manacher面试官反而不好确认你是真的理解还是背了模板。6. 真正容易踩的坑与测试方法6.1 我自己踩过的几个坑第一哨兵字符冲突。我在 Manacher 的预处理里用了 ^ 和 $如果原字符串恰好含有这两个字符整个算法就出问题了。LeetCode第5题原题约束字符串只包含数字和英文字母所以提交没问题。但在工程里或某些变形题中输入可能包含任意ASCII字符这时要么换成输入中不可能出现的控制字符比如 \u0000 或 \u0001要么在预处理前做一次检查。这个坑平时不显眼一旦踩到就非常隐蔽因为不是必现bug而是特定输入才出错。第二动态规划的遍历顺序。我之前在写 Dp 时习惯性地让 i 在外层、j 在内层结果用 abcba 这种用例一测发现读到的 dp[i1][j-1] 是默认 false输出结果只有1。排查了很久才意识到是填表顺序问题。记住动态规划里依赖的子问题没有先算好代码怎么调都是错的。这也是我为什么强调要按子串长度来外层循环。第三substring 的区间。Java 里 substring(a, b) 的左闭右开设计以及中心扩展返回 right - left - 1两个边界问题叠加起来特别容易写错。我建议在写完代码后用 aa 和 aba 这两个用例跑一下基本就能验证边界。第四Manacher 模板里 p[i] 的定义理解不同。网上搜题解会看到两种写法一种半径包含中心一种不包含中心。两者的初始化、while 循环条件、最终长度换算公式全都不一样。如果你混着背大概率写出一份又超时又越界的代码。我建议只吃透一种写法并且知道另一种写法存在的差异不要在考场上临时切换。6.2 一份可以直接复用的测试集每次写完这道题的代码我都习惯用下面的测试集验证覆盖常规情况、边界情况、全相同字符等输入期望输出说明空串边界aa单字符aaaa偶数长度回文aba 或 b无长度大于1的回文abaaba奇数长度回文cbbdbb偶数回文中心在字符间隙babadbab 或 aba多个等长结果可选aaaaaaaa全相同字符abcbaabcba回文在字符串中间abacdfgdcabaaba回文在开头且存在干扰子串这套用例覆盖面很全尤其是 cbbd 能帮你确认是否同时处理了奇数、偶数两类中心abacdfgdcaba 这类干扰用例能帮你确认是否误判了“包含回文”和“本身是回文”的区别。我爸在实际做题里见过不少人上来就上 Manacher结果因为某个边界条件没处理对调试时间比写代码还长。对于这道题中心扩展已经足够应对面试和日常需求Manacher 更多是锦上添花。我个人的建议是先在白板上把中心扩展写到无懈可击再去攻 Manacher两条腿走路才稳。