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

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^9109，在 Java 中可能超时（LeetCode 通常限制 1~2 秒）。因此需要更优解法。

2.3 回文的核心性质

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

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

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

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

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

四、完整答案（Java 实现）

4.1 方法一：动态规划

publicclassSolution{publicStringlongestPalindrome(Strings){intn=s.length();if(n<2)returns;intmaxLen=1;intbegin=0;boolean[][]dp=newboolean[n][n];char[]chars=s.toCharArray();// 边界条件：所有长度为1的子串都是回文for(inti=0;i<n;i++){dp[i][i]=true;}// 枚举子串长度 L 从 2 到 nfor(intL=2;L<=n;L++){for(inti=0;i<n;i++){intj=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;}}}returns.substring(begin,begin+maxLen);}}

4.2 方法二：中心扩展法

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

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

classSolution{publicStringlongestPalindrome(Strings){// 预处理：插入 '#' 统一奇偶StringBuildert=newStringBuilder("#");for(charc:s.toCharArray()){t.append(c).append('#');}Stringprocessed=t.toString();intn=processed.length();int[]armLen=newint[n];// 臂长数组intright=-1,center=-1;// 当前最右回文边界及其中心intmaxStart=0,maxEnd=0;// 最长回文在 processed 中的范围for(inti=0;i<n;i++){intcurArmLen;if(i<=right){intmirror=2*center-i;// i 关于 center 的对称点intminLen=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;}}// 提取原始字符（跳过 '#'）StringBuilderans=newStringBuilder();for(inti=maxStart;i<=maxEnd;i++){if(processed.charAt(i)!='#'){ans.append(processed.charAt(i));}}returnans.toString();}privateintexpand(Strings,intleft,intright){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 ) 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 动态规划三要素

1. 状态定义：dp[i][j]表示什么？
2. 状态转移：如何由子问题推导当前问题？
3. 边界条件：最小规模问题的解（如长度=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^5105，怎么办？

答：此时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"），安全系统需检测此类模式。

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

十二、相关题目推荐

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

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

十三、总结与延伸

13.1 核心收获

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

13.2 延伸思考

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

13.3 学习建议

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

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

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

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