最长回文子串算法详解：从暴力到Manacher

1. 最长回文串问题解析回文串是指正读反读都相同的字符串比如aba、abba都是回文串。在力扣hot100的第93题中我们需要找到一个字符串中的最长回文子串。这个问题看似简单但实际包含了多种解题思路和优化技巧。1.1 问题定义与示例给定一个字符串s找到s中最长的回文子串。例如输入babad输出bab或aba输入cbbd输出bb这个问题在字符串处理中非常经典也是面试中的高频题目。理解并掌握它的解法对于提升算法能力很有帮助。1.2 暴力解法分析最直观的解法是暴力枚举所有可能的子串然后检查是否为回文。这种方法的时间复杂度是O(n³)对于较长的字符串效率很低。def longestPalindrome(s): n len(s) if n 2: return s max_len 1 res s[0] for i in range(n-1): for j in range(i1, n): if j-i1 max_len and s[i:j1] s[i:j1][::-1]: max_len j-i1 res s[i:j1] return res虽然这种方法简单直接但在力扣上提交时会因为时间限制而无法通过所有测试用例。2. 中心扩展法详解中心扩展法是目前解决最长回文串问题最常用的方法之一时间复杂度为O(n²)空间复杂度为O(1)。2.1 基本思路回文串的中心可能是一个字符奇数长度或两个字符偶数长度。我们可以遍历字符串以每个字符或每对相邻字符为中心向两边扩展寻找最长的回文串。2.2 实现步骤遍历字符串中的每个字符作为可能的中心点分别考虑奇数长度和偶数长度的回文情况向左右两边扩展直到字符不匹配或到达边界记录找到的最长回文串def longestPalindrome(s): def expandAroundCenter(left, right): while left 0 and right len(s) and s[left] s[right]: left - 1 right 1 return s[left1:right] if len(s) 2: return s res for i in range(len(s)): # 奇数长度 odd expandAroundCenter(i, i) # 偶数长度 even expandAroundCenter(i, i1) if len(odd) len(res): res odd if len(even) len(res): res even return res2.3 复杂度分析时间复杂度O(n²)因为每个中心点最多扩展n次空间复杂度O(1)只使用了常数个额外变量3. 动态规划解法动态规划是另一种解决最长回文串问题的方法虽然时间复杂度也是O(n²)但思路有所不同。3.1 状态定义定义dp[i][j]表示字符串s从i到j的子串是否为回文串。3.2 状态转移方程当j - i 3时dp[i][j] (s[i] s[j])否则dp[i][j] (s[i] s[j]) and dp[i1][j-1]3.3 实现代码def longestPalindrome(s): n len(s) if n 2: return s dp [[False] * n for _ in range(n)] max_len 1 start 0 # 所有长度为1的子串都是回文 for i in range(n): dp[i][i] True # 检查长度为2的子串 for i in range(n-1): if s[i] s[i1]: dp[i][i1] True start i max_len 2 # 检查长度大于2的子串 for length in range(3, n1): for i in range(n - length 1): j i length - 1 if s[i] s[j] and dp[i1][j-1]: dp[i][j] True if length max_len: start i max_len length return s[start:startmax_len]3.4 复杂度分析时间复杂度O(n²)需要填充n²的DP表空间复杂度O(n²)需要存储DP表4. Manacher算法详解Manacher算法是解决最长回文串问题的最优算法时间复杂度为O(n)。4.1 算法思想Manacher算法通过预处理字符串和利用回文串的对称性质避免了重复计算。主要步骤包括预处理在字符间插入特殊字符如#统一处理奇偶长度维护一个数组P记录以每个字符为中心的最长回文半径利用对称性质减少计算量4.2 实现代码def longestPalindrome(s): # 预处理字符串 T #.join(^{}$.format(s)) n len(T) P [0] * n C R 0 for i in range(1, n-1): # 利用对称性 if i R: P[i] min(R - i, P[2*C - i]) # 尝试扩展 while T[i P[i] 1] T[i - P[i] - 1]: P[i] 1 # 更新中心和右边界 if i P[i] R: C, R i, i P[i] # 找到最大值 max_len, center max((n, i) for i, n in enumerate(P)) return s[(center - max_len)//2 : (center max_len)//2]4.3 复杂度分析时间复杂度O(n)每个字符最多被处理一次空间复杂度O(n)用于存储P数组5. 不同解法的比较与选择5.1 性能对比方法时间复杂度空间复杂度适用场景暴力法O(n³)O(1)仅适用于非常短的字符串中心扩展O(n²)O(1)一般情况下的首选动态规划O(n²)O(n²)理解动态规划的好例子ManacherO(n)O(n)需要最优解时使用5.2 选择建议面试中推荐使用中心扩展法容易解释且实现简单竞赛中可以使用Manacher算法获得最优性能学习时建议都实现一遍理解不同思路6. 常见错误与调试技巧6.1 边界条件处理空字符串或长度为1的字符串全相同字符的字符串没有回文子串的情况如abc6.2 性能优化提前终止当剩余长度小于当前最大长度时可以提前结束字符频率统计如果某个字符出现次数很少可以优先处理6.3 调试技巧打印中间结果在扩展过程中打印当前中心和扩展情况使用小例子先用简单例子验证算法正确性单元测试编写多个测试用例覆盖不同情况7. 力扣刷题建议7.1 刷题策略先理解问题再尝试解决从简单解法开始逐步优化比较不同解法的优劣记录解题思路和关键点7.2 相关题目推荐回文子串个数最长回文子序列最短回文串分割回文串7.3 力扣hot100刷题心得hot100是力扣上精选的100道高频面试题覆盖了各种算法和数据结构。建议按类别刷题字符串、数组、链表等每道题尝试多种解法总结常见模式和技巧定期复习做过的题目在解决最长回文串问题时我最初尝试了暴力解法但很快发现效率问题。转而学习中心扩展法后解题速度大幅提升。后来接触到Manacher算法虽然实现起来稍复杂但性能确实最优。建议初学者先从中心扩展法入手掌握后再挑战更高级的算法。