最长回文子串：中心扩展法与动态规划详解

1. 最长回文串问题解析回文串是算法面试中的经典题型指正读反读都相同的字符串。力扣hot100第93题要求找出给定字符串中的最长回文子串这个问题在技术面试中出现频率极高。我刷过上百道回文相关题目后发现掌握中心扩展法和动态规划两种解法就能应对大多数变种题。1.1 问题核心难点最长回文串问题的输入是一个字符串s要求输出其最长回文子串。例如输入babad → 输出bab或aba输入cbbd → 输出bb主要难点在于子串需要连续区别于子序列时间复杂度优化暴力解法O(n³)不可行边界条件处理单字符、双字符等情况2. 中心扩展法详解中心扩展法是我最推荐的回文串解法时间复杂度O(n²)空间复杂度O(1)既高效又容易理解。2.1 算法原理该算法的核心思想是把每个字符和每对相邻字符作为回文中心向两侧扩展直到不满足回文条件。具体步骤遍历字符串的每个位置i以i为中心向左右扩展奇数长度情况以i和i1为中心向左右扩展偶数长度情况记录扩展过程中发现的最长回文串def longestPalindrome(s: str) - str: def expand(l, r): while l 0 and r len(s) and s[l] s[r]: l - 1 r 1 return s[l1:r] res for i in range(len(s)): odd expand(i, i) # 奇数情况 even expand(i, i1) # 偶数情况 res max(res, odd, even, keylen) return res2.2 关键优化点提前终止当剩余未检查的字符串长度小于当前最大回文长度时可以直接跳出循环边界处理Python的字符串切片已经自动处理越界情况其他语言需要额外判断字符相等判断先比较最外层字符可以快速过滤不符合条件的情况注意中心扩展法在字符串全为相同字符时会退化为O(n²)但这种情况在实际面试中很少出现3. 动态规划解法虽然中心扩展法更优但动态规划解法也是面试官常考的解题思路体现了对状态转移的理解。3.1 状态定义定义dp[i][j]表示字符串s[i..j]是否为回文串状态转移方程dp[i][j] (s[i] s[j]) and (j - i 3 or dp[i1][j-1])解释首尾字符必须相等当子串长度≤3时只需首尾相等即为回文较长子串需要内部子串也是回文3.2 实现代码def longestPalindrome(s: str) - str: n len(s) dp [[False]*n for _ in range(n)] res for i in range(n-1, -1, -1): for j in range(i, n): dp[i][j] (s[i] s[j]) and (j - i 3 or dp[i1][j-1]) if dp[i][j] and (j - i 1) len(res): res s[i:j1] return res3.3 复杂度分析时间复杂度O(n²) 两重循环空间复杂度O(n²) DP表格存储适用场景当需要查询任意子串是否为回文时DP解法更有优势4. 马拉车算法Manacher虽然面试中不常要求但马拉车算法能在O(n)时间内解决问题适合进阶学习。4.1 算法核心思想对字符串进行预处理插入特殊字符如#统一奇偶情况维护一个回文半径数组P[i]表示以i为中心的最长回文半径利用对称性质减少重复计算4.2 代码实现def longestPalindrome(s: str) - str: T #.join(^{}$.format(s)) n len(T) P [0] * n C R 0 for i in range(1, n-1): P[i] (R i) and 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]5. 刷题实战技巧根据我刷hot100的经验分享几个提高通过率的关键技巧5.1 测试用例设计基础案例babad → bab/abacbbd → bb边界案例单字符a → a全相同字符aaaa → aaaa无回文abc → a性能案例长字符串1000字符5.2 常见错误排查下标越界扩展时忘记检查边界动态规划中循环顺序错误初始条件空字符串处理单字符直接返回更新结果忘记比较当前回文与最大回文长度切片范围错误5.3 面试应答策略先说明暴力解法(O(n³))及其缺点提出中心扩展法分析复杂度根据面试官要求可能需实现动态规划如果时间允许可以讨论马拉车算法主动提出测试用例验证代码正确性6. 性能对比与选择建议三种主要解法的对比算法时间复杂度空间复杂度实现难度适用场景中心扩展法O(n²)O(1)简单面试首选动态规划O(n²)O(n²)中等需要查询子串时马拉车算法O(n)O(n)困难超长字符串处理对于力扣hot100这类面试题我建议优先掌握中心扩展法理解动态规划的思路了解马拉车算法的存在即可在实际编码时中心扩展法约15行代码就能实现且容易解释清楚是面试时的最佳选择。我在最初刷题时曾过度追求马拉车算法后来发现面试中只需要说出思路即可不必现场实现。