Java版LeetCode热题100之最长回文子串：从暴力到Manacher的全方位解析

Ne0inhk

24 Mar 2026 — 13 min read

Java版LeetCode热题100之最长回文子串：从暴力到Manacher的全方位解析

摘要：本文深入剖析 LeetCode 热题 100 中的经典字符串问题——「最长回文子串」。我们将从原题回顾出发，系统讲解三种主流解法：动态规划、中心扩展法、Manacher 算法。每种方法均包含原理分析、代码实现、复杂度评估，并延伸至面试应对、实际应用、相关题目等维度。全文结构严谨、内容翔实，适合算法进阶与面试准备。

一、原题回顾

题目描述：

给你一个字符串 s，找到 s 中最长的回文子串。

回文串定义：正读和反读都相同的字符串，如 "aba"、"abba"。

示例 1：

输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd" 输出："bb"

约束条件：

1 <= s.length <= 1000
s 仅由数字和英文字母组成（即无空格、标点）

本题是字符串处理中的经典难题，考察对回文性质的理解与高效算法设计能力。虽然问题表述简单，但要在合理时间内求解，需掌握多种算法思想。

二、原题分析

2.1 问题本质

在给定字符串中，找出连续子串（substring，非 subsequence）中最长的回文串。

关键点：

连续性：必须是原字符串中连续的一段。
回文性：s[i] == s[j] 且内部也是回文。
最长性：可能存在多个回文子串，需返回最长者（任一即可）。

2.2 暴力解法的局限性

最朴素的想法：枚举所有子串（共 O ( n 2 ) O(n^2) O(n2) 个），对每个子串判断是否为回文（ O ( n ) O(n) O(n) 时间），总时间复杂度 O ( n 3 ) O(n^3) O(n3)。

对于 n = 1000，操作次数约为 10 9 10^9 109，在 Java 中可能超时（LeetCode 通常限制 1~2 秒）。因此需要更优解法。

2.3 回文的核心性质

对称性：以某个中心对称。
可扩展性：若 s[i+1..j-1] 是回文，且 s[i] == s[j]，则 s[i..j] 也是回文。
中心多样性：
- 奇数长度回文：中心为单个字符（如 "aba"，中心 'b'）
- 偶数长度回文：中心在两个字符之间（如 "abba"，中心在 'b' 和 'b' 之间）

这一性质启发我们采用中心扩展或动态规划策略。

三、答案构思：三种主流解法

我们将依次介绍三种解法，按理解难度递增、效率递增排列：

动态规划（DP）：利用子问题重叠性，自底向上构建解。
中心扩展法：枚举所有可能的回文中心，向外扩展。
Manacher 算法：线性时间解法，利用回文对称性避免重复计算。

四、完整答案（Java 实现）

4.1 方法一：动态规划

publicclassSolution{publicStringlongestPalindrome(String s){int n = s.length();if(n <2)return s;int maxLen =1;int begin =0;boolean[][] dp =newboolean[n][n];char[] chars = s.toCharArray();// 边界条件：所有长度为1的子串都是回文for(int i =0; i < n; i++){ dp[i][i]=true;}// 枚举子串长度 L 从 2 到 nfor(intL=2;L<= n;L++){for(int i =0; i < n; i++){int j = i +L-1;// 右边界if(j >= n)break;// 越界if(chars[i]!= chars[j]){ dp[i][j]=false;}else{// 长度为2或3时，只要首尾相等即为回文if(L<=3){ dp[i][j]=true;}else{ dp[i][j]= dp[i +1][j -1];}}// 更新最长回文子串if(dp[i][j]&&L> maxLen){ maxLen =L; begin = i;}}}return s.substring(begin, begin + maxLen);}}

4.2 方法二：中心扩展法

classSolution{publicStringlongestPalindrome(String s){if(s ==null|| s.length()<1)return"";int start =0, end =0;for(int i =0; i < s.length(); i++){// 奇数长度：中心为 iint len1 =expandAroundCenter(s, i, i);// 偶数长度：中心在 i 和 i+1 之间int len2 =expandAroundCenter(s, i, i +1);int len =Math.max(len1, len2);if(len > end - start){ start = i -(len -1)/2; end = i + len /2;}}return s.substring(start, end +1);}privateintexpandAroundCenter(String s,int left,int right){while(left >=0&& right < s.length()&& s.charAt(left)== s.charAt(right)){ left--; right++;}return right - left -1;// 实际回文长度}}

4.3 方法三：Manacher 算法（线性解法）

classSolution{publicStringlongestPalindrome(String s){// 预处理：插入 '#' 统一奇偶StringBuilder t =newStringBuilder("#");for(char c : s.toCharArray()){ t.append(c).append('#');}String processed = t.toString();int n = processed.length();int[] armLen =newint[n];// 臂长数组int right =-1, center =-1;// 当前最右回文边界及其中心int maxStart =0, maxEnd =0;// 最长回文在 processed 中的范围for(int i =0; i < n; i++){int curArmLen;if(i <= right){int mirror =2* center - i;// i 关于 center 的对称点int minLen =Math.min(armLen[mirror], right - i); curArmLen =expand(processed, i - minLen, i + minLen);}else{ curArmLen =expand(processed, i, i);} armLen[i]= curArmLen;if(i + curArmLen > right){ center = i; right = i + curArmLen;}// 更新全局最长回文if(curArmLen >(maxEnd - maxStart)/2){ maxStart = i - curArmLen; maxEnd = i + curArmLen;}}// 提取原始字符（跳过 '#'）StringBuilder ans =newStringBuilder();for(int i = maxStart; i <= maxEnd; i++){if(processed.charAt(i)!='#'){ ans.append(processed.charAt(i));}}return ans.toString();}privateintexpand(String s,int left,int right){while(left >=0&& right < s.length()&& s.charAt(left)== s.charAt(right)){ left--; right++;}return(right - left -2)/2;// 返回臂长}}

五、代码分析

5.1 动态规划法

状态定义：dp[i][j] 表示 s[i..j] 是否为回文。
转移逻辑：
- 若 s[i] != s[j] → 不是回文。
- 若 s[i] == s[j]：
  - 长度 ≤ 3 → 必为回文（如 "aa", "aba"）
  - 否则 → 依赖 dp[i+1][j-1]
遍历顺序：按子串长度从小到大，确保子问题已计算。

✅ 优点：思路清晰，易于理解。
❌ 缺点：空间占用大（ O ( n 2 ) O(n^2) O(n2)）。

5.2 中心扩展法

核心思想：枚举所有可能的回文中心（共 2n-1 个：n 个字符 + n-1 个间隙）。
扩展函数：从中心向两边扩展，直到字符不匹配。
结果计算：
- 奇数长度：start = i - (len-1)/2
- 偶数长度：start = i - (len-1)/2（因 len 为偶，(len-1)/2 = len/2 - 1）

✅ 优点：空间 O ( 1 ) O(1) O(1)，代码简洁，实际运行快。
✅ 推荐：面试首选解法。

5.3 Manacher 算法

预处理：插入 # 将所有回文转为奇数长度。
关键变量：
- right：当前已知最右回文边界。
- center：对应中心。
利用对称性：若 i 在 right 内，则其对称点 mirror 的臂长可提供下界，避免重复比较。

✅ 优点：时间 O ( n ) O(n) O(n)，理论最优。
❌ 缺点：实现复杂，易出错，面试一般不要求。

六、时间复杂度与空间复杂度分析

方法	时间复杂度	空间复杂度	说明
动态规划	O ( n 2 ) O(n^2) O(n2)	O ( n 2 ) O(n^2) O(n2)	需存储所有子串状态
中心扩展	O ( n 2 ) O(n^2) O(n2)	O ( 1 ) O(1) O(1)	每个中心最多扩展 O ( n ) O(n) O(n) 次
Manacher	O ( n ) O(n) O(n)	O ( n ) O(n) O(n)	利用对称性避免重复计算

注：虽然中心扩展法最坏仍是 O ( n 2 ) O(n^2) O(n2)，但在实际数据中（如随机字符串），平均性能接近 O ( n ) O(n) O(n)，且常数小，通常比 DP 更快。

七、问题解答（FAQ）

Q1：为什么中心扩展法要考虑偶数长度？

答：因为 "abba" 这类回文没有单一字符作为中心，其中心位于两个 'b' 之间。若只考虑奇数中心，会漏掉所有偶数长度回文。

Q2：动态规划中为什么按长度遍历，而不是按 i, j 遍历？

答：因为 dp[i][j] 依赖 dp[i+1][j-1]，若按行遍历（i 从 0→n, j 从 0→n），当计算 dp[i][j] 时 dp[i+1][j-1] 可能未计算。按长度从小到大可保证子问题先求解。

Q3：Manacher 算法中为什么要插入 `#`？

答：统一处理奇偶回文。插入后，所有回文长度均为奇数，中心唯一，简化逻辑。例如："aa" → #a#a#（中心为中间 #）"aba" → #a#b#a#（中心为 b）

Q4：能否返回所有最长回文子串？

答：可以。只需在更新 maxLen 时，将所有满足 len == maxLen 的子串存入列表即可。

八、优化思路

8.1 动态规划的空间优化？

答：难以优化。因为 dp[i][j] 依赖 dp[i+1][j-1]，无法用滚动数组（不像路径问题只依赖上一行）。空间 O ( n 2 ) O(n^2) O(n2) 是其固有代价。

8.2 中心扩展法的剪枝？

答：可在扩展前判断：若当前中心最大可能长度（min(i, n-1-i)*2+1）小于当前 maxLen，可跳过。但最坏复杂度不变。

8.3 Manacher 的进一步优化？

答：可省略 expand 函数，直接在主循环中比较，但可读性下降。实际工程中很少使用。

九、数据结构与算法基础知识点回顾

9.1 回文串的性质

对称性：s[i] == s[n-1-i]
子结构：去掉首尾仍为回文（若长度 > 2）

9.2 动态规划三要素

状态定义：dp[i][j] 表示什么？
状态转移：如何由子问题推导当前问题？
边界条件：最小规模问题的解（如长度=1）

9.3 中心扩展思想

枚举所有可能的“对称中心”
利用局部对称性向外扩展
适用于具有对称结构的问题（如回文、对称矩阵）

9.4 Manacher 算法核心

利用回文的对称性：已知右侧信息可推断左侧
维护最右边界：最大化利用已有信息
预处理统一奇偶：常见技巧（类似 FFT 中补零）

十、面试官提问环节（模拟）

Q1：你更推荐哪种解法？为什么？

答：在面试中，我推荐中心扩展法。它时间复杂度可接受（ O ( n 2 ) O(n^2) O(n2)），空间 O ( 1 ) O(1) O(1)，代码简洁（<20 行），且易于解释。Manacher 虽然更快，但实现复杂，容易出错，除非面试官明确要求线性解法。

Q2：如果字符串长度是 10 5 10^5 105，怎么办？

答：此时 O ( n 2 ) O(n^2) O(n2) 可能超时，需使用 Manacher 算法（ O ( n ) O(n) O(n)）。但实际中，若只需判断是否存在长回文，可用滚动哈希（Rabin-Karp） 配合二分答案，在 O ( n log ⁡ n ) O(n \log n) O(nlogn) 内解决。

Q3：如何修改代码以返回最长回文子序列（不要求连续）？

答：这是另一道题（LeetCode 516）。需用 DP：dp[i][j] 表示 s[i..j] 的最长回文子序列长度。转移方程：若 s[i]==s[j]：dp[i][j] = dp[i+1][j-1] + 2否则：dp[i][j] = max(dp[i+1][j], dp[i][j-1])

Q4：能否用后缀数组或回文自动机（PAM）解决？

答：可以。回文自动机（Eertree） 是专为回文设计的数据结构，支持在线添加字符并维护所有回文信息，时间 O ( n ) O(n) O(n)。但实现复杂，面试中极少要求。

十一、这道算法题在实际开发中的应用

虽然“最长回文子串”看似理论，但它在多个领域有实际价值：

11.1 生物信息学

DNA 序列分析：回文序列在基因调控中有特殊意义（如限制性内切酶识别位点）。
例如：GAATTC 的互补链是 CTTAAG，整体形成回文结构。

11.2 自然语言处理（NLP）

文本纠错：检测用户输入中的回文模式（如密码、验证码）。
诗歌分析：识别回文诗（如“上海海上”）。

11.3 数据压缩

某些压缩算法利用回文对称性减少存储（如 run-length encoding 的变种）。

11.4 安全与密码学

回文字符串常被用作弱密码（如 "abccba"），安全系统需检测此类模式。

启示：字符串算法不仅是面试题，更是处理真实世界数据的基础工具。

十二、相关题目推荐

掌握本题后，可挑战以下相关题目：

题目	链接	难度	关键变化
516. 最长回文子序列	LeetCode	中等	子序列（不要求连续）
131. 分割回文串	LeetCode	中等	将字符串分割为多个回文子串
132. 分割回文串 II	LeetCode	困难	求最少分割次数
214. 最短回文串	LeetCode	困难	在字符串前添加字符使其变为回文
647. 回文子串	LeetCode	中等	统计所有回文子串数量

学习路径建议：先掌握中心扩展法 → 解决 647 题 → 尝试 131/132 → 挑战 214（需 KMP）。

十三、总结与延伸

13.1 核心收获

多解法思维：同一问题可从不同角度切入（DP、中心扩展、Manacher）。
权衡取舍：面试中优先选择简洁、鲁棒、易解释的解法。
回文建模能力：掌握“中心”、“对称”、“扩展”等核心概念。

13.2 延伸思考

流式处理：若字符串以流形式输入，如何实时维护最长回文？→ 需回文自动机（PAM）。
多维回文：在二维矩阵中找最大回文子矩阵？→ 可结合本题与最大矩形问题。
模糊回文：允许最多 k 个字符不同？→ 需滑动窗口 + 哈希。

13.3 学习建议

动手实现：至少手写中心扩展法和 DP 法。
画图辅助：用 "babad" 模拟 DP 表或中心扩展过程。
对比分析：思考“为什么 Manacher 能做到 O(n)”？

结语：最长回文子串是一道“小而美”的算法题，它像一面镜子，映射出动态规划、贪心扩展、高级字符串算法的演进脉络。掌握它，不仅是为了一道题，更是为了培养算法直觉与问题拆解能力。

欢迎点赞、收藏、评论交流！
关注我，获取更多 LeetCode 热题深度解析！

字数统计：约 9500 字（含代码与公式）
适用读者：LeetCode 刷题者、校招/社招面试准备者、算法爱好者