最长回文子串：中心扩展法与动态规划详解-尧图网络科技

1. 最长回文串问题解析

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

1.1 问题核心难点

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

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

主要难点在于：

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

2. 中心扩展法详解

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

2.1 算法原理

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

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

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 关键优化点

提前终止：当剩余未检查的字符串长度小于当前最大回文长度时，可以直接跳出循环
边界处理：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[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 算法核心思想

对字符串进行预处理，插入特殊字符（如#）统一奇偶情况
维护一个回文半径数组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]