图解回文子串：三种中心扩散法的Python实现与实战

回文串问题一直是算法面试中的高频考点，但很多学习者陷入动态规划的状态转移公式记忆困境。实际上，中心扩散法提供了一种更直观、空间效率更高的解题思路。本文将用Python代码和可视化图解，带你掌握三种中心扩散技巧，并对比分析其与动态规划的优劣。

1. 中心扩散法的核心思想

中心扩散法的基本思路是从字符串的每一个可能的中心点向两侧扩展，判断是否满足回文条件。与动态规划相比，这种方法不需要额外的二维数组存储状态，空间复杂度从O(n²)降至O(1)。

理解中心扩散的关键在于区分奇偶两种情况：

• 奇数长度：中心点为单个字符（如"aba"的中心是'b'）
• 偶数长度：中心点为两个相同字符之间的空隙（如"abba"的中心在两个'b'之间）

def expand_around_center(s, left, right):
    """中心扩散辅助函数"""
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return right - left - 1  # 返回回文长度

2. 基础中心扩散实现

我们先看最基本的中心扩散实现，以解决LeetCode 647（统计所有回文子串）为例：

def count_substrings(s: str) -> int:
    count = 0
    n = len(s)
    
    for i in range(n):
        # 奇数长度
        l, r = i, i
        while l >=0 and r < n and s[l] == s[r]:
            count += 1
            l -= 1
            r += 1
        
        # 偶数长度
        l, r = i, i+1
        while l >=0 and r < n and s[l] == s[r]:
            count += 1
            l -= 1
            r += 1
    
    return count

时间复杂度分析：

• 外层循环遍历n个中心点
• 内层while循环最多执行n/2次
• 总体时间复杂度仍为O(n²)，但实际运行效率通常优于动态规划

3. 优化版中心扩散：记录最长回文

对于LeetCode 5（最长回文子串），我们可以在扩散过程中记录当前最长回文的起止位置：

def longest_palindrome(s: str) -> str:
    if not s: return ""
    
    start, end = 0, 0
    
    for i in range(len(s)):
        len1 = expand_around_center(s, i, i)   # 奇数
        len2 = expand_around_center(s, i, i+1) # 偶数
        max_len = max(len1, len2)
        
        if max_len > end - start:
            start = i - (max_len - 1) // 2
            end = i + max_len // 2
    
    return s[start:end+1]

性能对比：

4. 马拉车算法(Manacher's Algorithm)

虽然中心扩散法已经优化了空间复杂度，但马拉车算法进一步将时间复杂度降至O(n)。其核心思想是通过对称性利用已知信息：

def manacher(s: str) -> str:
    # 预处理字符串
    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((v, i) for i, v in enumerate(P))
    return s[(center - max_len) // 2: (center + max_len) // 2]

算法关键点：

1. 预处理字符串，统一处理奇偶情况
2. 维护当前最右回文边界R和其中心C
3. 利用对称性减少不必要的比较

5. 实战应用与选择建议

不同场景下的方法选择：

• 面试快速实现：基础中心扩散法
• 追求极致性能：马拉车算法
• 需要中间状态：动态规划（如分割回文串问题）

常见误区提醒：

1. 忘记处理偶数长度情况
2. 边界条件处理不当（如空字符串或单字符）
3. 在LeetCode 647中重复计算相同中心

对于回文子序列问题（如LeetCode 516），动态规划仍是更合适的选择，因为中心扩散法难以处理不连续的序列。