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

1. 最长回文串问题解析

回文串是算法面试中的经典题型，指正读反读都相同的字符串。力扣hot100第93题要求找出给定字符串中的最长回文子串，这个问题在技术面试中出现频率极高。我刷过上百道回文相关题目后，发现掌握中心扩展法和动态规划两种解法就能应对大多数变种题。

1.1 问题核心难点

最长回文串问题的输入是一个字符串s，要求输出其最长回文子串。例如：

• 输入："babad" → 输出："bab"或"aba"
• 输入："cbbd" → 输出："bb"

主要难点在于：

1. 子串需要连续（区别于子序列）
2. 时间复杂度优化（暴力解法O(n³)不可行）
3. 边界条件处理（单字符、双字符等情况）

2. 中心扩展法详解

中心扩展法是我最推荐的回文串解法，时间复杂度O(n²)，空间复杂度O(1)，既高效又容易理解。

2.1 算法原理

该算法的核心思想是：把每个字符和每对相邻字符作为回文中心，向两侧扩展直到不满足回文条件。具体步骤：

1. 遍历字符串的每个位置i
2. 以i为中心向左右扩展（奇数长度情况）
3. 以i和i+1为中心向左右扩展（偶数长度情况）
4. 记录扩展过程中发现的最长回文串

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[l+1:r] res = "" for i in range(len(s)): odd = expand(i, i) # 奇数情况 even = expand(i, i+1) # 偶数情况 res = max(res, odd, even, key=len) return res

2.2 关键优化点

1. 提前终止：当剩余未检查的字符串长度小于当前最大回文长度时，可以直接跳出循环
2. 边界处理：Python的字符串切片已经自动处理越界情况，其他语言需要额外判断
3. 字符相等判断：先比较最外层字符可以快速过滤不符合条件的情况

注意：中心扩展法在字符串全为相同字符时会退化为O(n²)，但这种情况在实际面试中很少出现

3. 动态规划解法

虽然中心扩展法更优，但动态规划解法也是面试官常考的解题思路，体现了对状态转移的理解。

3.1 状态定义

定义dp[i][j]表示字符串s[i..j]是否为回文串，状态转移方程：

dp[i][j] = (s[i] == s[j]) and (j - i < 3 or dp[i+1][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[i+1][j-1]) if dp[i][j] and (j - i + 1) > len(res): res = s[i:j+1] return res

3.3 复杂度分析

• 时间复杂度：O(n²) 两重循环
• 空间复杂度：O(n²) DP表格存储
• 适用场景：当需要查询任意子串是否为回文时，DP解法更有优势

4. 马拉车算法（Manacher）

虽然面试中不常要求，但马拉车算法能在O(n)时间内解决问题，适合进阶学习。

4.1 算法核心思想

1. 对字符串进行预处理，插入特殊字符（如#）统一奇偶情况
2. 维护一个回文半径数组P[i]表示以i为中心的最长回文半径
3. 利用对称性质减少重复计算

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 测试用例设计

1. 基础案例：
   • "babad" → "bab"/"aba"
   • "cbbd" → "bb"
2. 边界案例：
   • 单字符："a" → "a"
   • 全相同字符："aaaa" → "aaaa"
   • 无回文："abc" → "a"
3. 性能案例：
   • 长字符串（1000+字符）

5.2 常见错误排查

1. 下标越界：
   • 扩展时忘记检查边界
   • 动态规划中循环顺序错误
2. 初始条件：
   • 空字符串处理
   • 单字符直接返回
3. 更新结果：
   • 忘记比较当前回文与最大回文长度
   • 切片范围错误

5.3 面试应答策略

1. 先说明暴力解法(O(n³))及其缺点
2. 提出中心扩展法，分析复杂度
3. 根据面试官要求，可能需实现动态规划
4. 如果时间允许，可以讨论马拉车算法
5. 主动提出测试用例验证代码正确性

6. 性能对比与选择建议

三种主要解法的对比：

对于力扣hot100这类面试题，我建议：

1. 优先掌握中心扩展法
2. 理解动态规划的思路
3. 了解马拉车算法的存在即可

在实际编码时，中心扩展法约15行代码就能实现，且容易解释清楚，是面试时的最佳选择。我在最初刷题时曾过度追求马拉车算法，后来发现面试中只需要说出思路即可，不必现场实现。