摘要最长回文子串是字符串处理中的经典问题也是面试中的高频考点。本文深入解析LeetCode第5题系统讲解中心扩展法和动态规划两种主流解法从算法原理、代码实现到时间空间复杂度分析全方位覆盖。通过多组测试用例验证算法正确性并延伸探讨Manacher算法的进阶优化思路。一、问题定义与背景1.1 问题描述给定一个字符串s找到其中的最长回文子串并返回该子串。如果存在多个长度相同的最长回文子串可以返回任意一个。示例 1输入s babad 输出bab 或 aba两者都是最长回文子串示例 2输入s cbbd 输出bb1.2 回文串的定义回文串是指正读和反读都相同的字符串。例如奇数长度回文aba,abcba,racecar偶数长度回文aa,abba,noon1.3 问题的难点最长回文子串问题看似简单实际上存在几个核心挑战回文中心的多样性奇数长度回文的中心是单个字符偶数长度回文的中心是两个字符之间的空隙边界判断需要正确处理字符串的首尾边界时间效率暴力枚举所有子串的时间复杂度为O(n3)O(n^3)O(n3)需要优化二、中心扩展法2.1 算法思想中心扩展法的核心思想是回文串是关于中心对称的。对于每个可能的回文中心我们向两边扩展检查对称位置的字符是否相同。扩展直到遇到不匹配的字符或到达边界为止。2.2 中心点的选择奇数长度回文的中心字符串中的每个字符n个中心偶数长度回文的中心相邻字符之间的空隙n-1个中心总共需要检查2n-1个中心点。2.3 代码实现deflongestPalindrome(s:str)-str: 中心扩展法解决最长回文子串问题 时间复杂度O(n²) 空间复杂度O(1) ifnotsorlen(s)1:returnsdefexpand_around_center(left:int,right:int)-tuple:从中心向两边扩展返回回文串的起止位置whileleft0andrightlen(s)ands[left]s[right]:left-1right1returnleft1,right-1start,end0,0foriinrange(len(s)):# 奇数长度回文以 s[i] 为中心left1,right1expand_around_center(i,i)# 偶数长度回文以 s[i] 和 s[i1] 之间的空隙为中心left2,right2expand_around_center(i,i1)# 更新最长回文串ifright1-left1end-start:start,endleft1,right1ifright2-left2end-start:start,endleft2,right2returns[start:end1]2.4 复杂度分析时间复杂度O(n2)O(n^2)O(n2)外层循环遍历n个字符内层expand_around_center最坏情况下扩展O(n)O(n)O(n)次总计O(n2)O(n^2)O(n2)空间复杂度O(1)O(1)O(1)只使用了常数个额外变量2.5 算法可视化以字符串babad为例位置: 0 1 2 3 4 字符: b a b a d ↑ ↑ 中心2 ← → (扩展得到 bab 或 aba)三、动态规划法3.1 动态规划思想动态规划的核心是状态定义和状态转移。状态定义dp[i][j]表示字符串s[i:j1]包含索引i到j的子串是否为回文串状态转移dp[i][j] true当且仅当s[i] s[j]首尾字符相同且j - i 2子串长度为 1 或 2或dp[i1][j-1] true内部子串是回文3.2 遍历顺序状态转移依赖dp[i1][j-1]即左下角的状态。因此必须从短子串向长子串遍历即按子串长度递增的顺序遍历。3.3 代码实现deflongestPalindrome_dp(s:str)-str: 动态规划解决最长回文子串问题 时间复杂度O(n²) 空间复杂度O(n²) nlen(s)ifn2:returns# dp[i][j] 表示 s[i:j1] 是否为回文串dp[[False]*nfor_inrange(n)]# 初始化所有长度为1的子串都是回文foriinrange(n):dp[i][i]Truestart,max_len0,1# 按子串长度枚举forlengthinrange(2,n1):foriinrange(n-length1):jilength-1# 判断 s[i:j1] 是否为回文ifs[i]s[j]:iflength2:dp[i][j]Trueelse:dp[i][j]dp[i1][j-1]# 更新最长回文串ifdp[i][j]andlengthmax_len:start,max_leni,lengthreturns[start:startmax_len]3.4 复杂度分析时间复杂度O(n2)O(n^2)O(n2)两层循环遍历所有子串子串总数为n(n1)2\frac{n(n1)}{2}2n(n1)​空间复杂度O(n2)O(n^2)O(n2)需要n × n的二维数组存储状态3.5 空间优化版本我们可以只记录起始位置和长度不需要完整的 DP 表deflongestPalindrome_optimized(s:str)-str:空间优化的动态规划nlen(s)ifn2:returns start,max_len0,1# dp[i][j] 仅依赖 dp[i1][j-1]可以用一维数组优化# 但为了代码清晰这里保留二维数组的思想forlengthinrange(2,n1):foriinrange(n-length1):jilength-1ifs[i]s[j]and(length3orTrue):# length 3 时无需检查中间iflengthmax_len:start,max_leni,lengthreturns[start:startmax_len]四、进阶算法Manacher 算法4.1 算法思想Manacher 算法能在O(n)O(n)O(n)时间复杂度内解决最长回文子串问题是该问题的最优解法。核心思想是利用已经计算过的回文串信息来加速后续的计算。4.2 关键概念回文半径radius[i]以位置i为中心的回文串的半径长度最右边界right已知的所有回文串能达到的最右位置中心center使right达到最大的回文中心4.3 代码实现defmanacher(s:str)-str: Manacher 算法 - O(n) 时间复杂度 时间复杂度O(n) 空间复杂度O(n) # 预处理插入分隔符使奇偶回文统一处理t##.join(s)#nlen(t)radius[0]*n# 回文半径数组centerright0max_len,max_center0,0foriinrange(n):# 计算最小回文半径ifiright:mirror2*center-i radius[i]min(right-i,radius[mirror])# 向两边扩展whilei-radius[i]-10andiradius[i]1n:ift[i-radius[i]-1]t[iradius[i]1]:radius[i]1else:break# 更新右边界和中心ifiradius[i]right:center,righti,iradius[i]# 记录最长回文ifradius[i]max_len:max_lenradius[i]max_centeri# 还原原始字符串中的最长回文子串start(max_center-max_len)//2returns[start:startmax_len]4.4 复杂度分析时间复杂度O(n)O(n)O(n)空间复杂度O(n)O(n)O(n)五、算法对比与选择算法时间复杂度空间复杂度代码复杂度推荐场景暴力枚举O(n3)O(n^3)O(n3)O(1)O(1)O(1)低不推荐中心扩展O(n2)O(n^2)O(n2)O(1)O(1)O(1)中面试首选动态规划O(n2)O(n^2)O(n2)O(n2)O(n^2)O(n2)中需要回文信息时ManacherO(n)O(n)O(n)O(n)O(n)O(n)高追求最优性能面试建议推荐回答顺序先介绍中心扩展法直观、实现简单分析其时间复杂度O(n2)O(n^2)O(n2)提到可以用 Manacher 算法优化到O(n)O(n)O(n)如果面试官不追问具体实现中心扩展法足够六、测试用例验证deftest_longest_palindrome():# 基本测试assertlongestPalindrome(babad)in[bab,aba]assertlongestPalindrome(cbbd)bb# 边界测试assertlongestPalindrome()assertlongestPalindrome(a)aassertlongestPalindrome(ac)in[a,c]# 全回文测试assertlongestPalindrome(racecar)racecarassertlongestPalindrome(aaaa)aaaa# 长字符串测试sa*1000assertlongestPalindrome(s)sprint(所有测试用例通过!)test_longest_palindrome()七、相关扩展问题7.1 最长回文子序列区别于子串连续子序列可以不连续deflongestPalindromeSubseq(s:str)-int:LeetCode 516: 最长回文子序列nlen(s)dp[[0]*nfor_inrange(n)]foriinrange(n):dp[i][i]1foriinrange(n-1,-1,-1):forjinrange(i1,n):ifs[i]s[j]:dp[i][j]dp[i1][j-1]2else:dp[i][j]max(dp[i1][j],dp[i][j-1])returndp[0][n-1]7.2 最短回文分割将字符串分割成回文子串求最少分割次数defminCut(s:str)-int:LeetCode 132: 分割回文串 IInlen(s)ifn1:return0# 预处理判断所有子串是否为回文is_pal[[False]*nfor_inrange(n)]foriinrange(n):is_pal[i][i]Trueforlengthinrange(2,n1):foriinrange(n-length1):jilength-1is_pal[i][j](s[i]s[j])and(length3oris_pal[i1][j-1])# dp[i] 表示 s[0:i1] 的最少分割次数dplist(range(n))foriinrange(n):ifall(is_pal[0][i]):dp[i]0continueforjinrange(i):ifis_pal[j1][i]:dp[i]min(dp[i],dp[j]1)returndp[n-1]八、总结核心要点中心扩展法是最实用的面试解法核心思想是回文关于中心对称动态规划通过状态定义将问题拆解需要注意遍历顺序Manacher 算法是最优解但实现较复杂面试中了解思路即可回文问题可以预处理来加速如 Manacher 中的分隔符技巧面试话术“这道题的核心观察是回文串关于中心对称。我会采用中心扩展法对每个可能的回文中心奇数长度是字符偶数长度是字符间隙向两边扩展直到遇到不匹配的字符。时间复杂度是O(n2)O(n^2)O(n2)空间复杂度是O(1)O(1)O(1)。如果需要O(n)O(n)O(n)的最优解可以用 Manacher 算法利用已计算的回文信息来加速。”参考文献LeetCode. (2024). 5. Longest Palindromic Substring. https://leetcode.com/problems/longest-palindromic-substring/Manacher, G. (1975). A new linear-time on-line algorithm for finding the smallest starting point for a palindrome in a string.Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.). MIT Press.