【Python 千题 —— 算法篇】寻找最长回文子串

题目背景

回文串是指一个字符串从左到右和从右到左读都是一样的。寻找一个字符串中的最长回文子串是许多经典算法问题之一，广泛应用于文本处理、数据分析和计算生物学等领域。

本题的挑战在于如何高效地找出最长的回文子串。在暴力搜索可能导致时间复杂度过高的情况下，掌握优化算法不仅可以提升代码性能，还能加深我们对字符串处理的理解。

题目描述

给定一个字符串 s，请你找出其中最长的回文子串。你可以假设 s 的最大长度为 1000。

输入描述

• 一个字符串 s，长度在 [1, 1000] 之间，且字符为小写字母。

输出描述

• 一个字符串，表示输入字符串中最长的回文子串。

示例

示例 ①

输入：

# 调用 longestPalindrome() 函数
print(longestPalindrome("babad"))

输出：

"bab"

解释：回文子串有 “bab” 和 “aba”，长度均为 3，返回其中一个即可。

示例 ②

输入：

print(longestPalindrome("cbbd"))

输出：

"bb"

解释：最长回文子串是 “bb”。

代码讲解与多种解法

解法一：暴力搜索法

最直接的解法是使用暴力搜索法，检查每一个子串是否为回文，并在检查时记录最长的回文子串。虽然该方法简单易懂，但它的时间复杂度为 O(n^3)，对于较长的字符串来说效率较低。

def longestPalindrome(s):
    def is_palindrome(substring):
        return substring == substring[::-1]

    n = len(s)
    max_len = 0
    start = 0

    for i in range(n):
        for j in range(i, n):
            if is_palindrome(s[i:j+1]) and (j - i + 1) > max_len:
                max_len = j - i + 1
                start = i

    return s[start:start + max_len]

优点：

• 实现简单直观，易于理解。

缺点：

• 时间复杂度为 O(n^3)，对于长字符串性能较差。

解法二：中心扩展法

中心扩展法通过从字符串的每个位置向外扩展，寻找回文子串。这种方法利用回文串的对称性，能在 O(n^2) 的时间复杂度内找到最长的回文子串，较暴力搜索法有明显的性能提升。

def longestPalindrome(s):
    if not s or len(s) == 1:
        return s

    def expand_around_center(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1:right]

    max_palindrome = ""
    for i in range(len(s)):
        odd_palindrome = expand_around_center(i, i)
        even_palindrome = expand_around_center(i, i + 1)
        max_palindrome = max(odd_palindrome, even_palindrome, max_palindrome, key=len)

    return max_palindrome

优点：

• 时间复杂度为 O(n^2)，较为高效。
• 代码较简洁，且适用于大多数实际场景。

缺点：

• 对于极端大数据量，仍然可能存在性能瓶颈。

解法三：动态规划法

动态规划法通过构建一个二维表来记录子串是否为回文，以此减少重复计算的次数。其时间复杂度同样为 O(n^2)，但在空间复杂度上会有额外的消耗 O(n^2)，适用于需要明确记录所有回文状态的情况。

def longestPalindrome(s):
    n = len(s)
    if n == 0:
        return ""
    
    dp = [[False] * n for _ in range(n)]
    start, max_len = 0, 1
    
    for i in range(n):
        dp[i][i] = True
    
    for end in range(1, n):
        for start in range(end):
            if s[start] == s[end]:
                if end - start == 1 or dp[start + 1][end - 1]:
                    dp[start][end] = True
                    if end - start + 1 > max_len:
                        max_len = end - start + 1
                        longest_palindrome_start = start

    return s[longest_palindrome_start:longest_palindrome_start + max_len]

优点：

• 可以记录所有子串的回文状态，便于追溯具体情况。
• 理论上稳定的 O(n^2) 时间复杂度，适合分析数据时使用。

缺点：

• 额外的 O(n^2) 空间复杂度，可能会导致空间使用过大。

解法四：马拉车算法

马拉车算法（Manacher’s Algorithm）是一种线性时间复杂度 O(n) 的算法。它利用回文的对称性，特别适合用于寻找最长回文子串。这是解决该问题的最优解，但其实现较为复杂。

def longestPalindrome(s):
    t = '#' + '#'.join(s) + '#'
    n = len(t)
    p = [0] * n
    c = r = 0
    max_center = 0
    
    for i in range(n):
        mirror = 2 * c - i
        if i < r:
            p[i] = min(r - i, p[mirror])
        
        while i + p[i] + 1 < n and i - p[i] - 1 >= 0 and t[i + p[i] + 1] == t[i - p[i] - 1]:
            p[i] += 1
        
        if i + p[i] > r:
            c, r = i, i + p[i]
        
        if p[i] > p[max_center]:
            max_center = i
    
    start = (max_center - p[max_center]) // 2
    return s[start:start + p[max_center]]

优点：

• 时间复杂度为 O(n)，是最优解，适用于需要极高效率的场景。
• 对称性处理巧妙，可提升处理大数据集时的性能。

缺点：

• 实现复杂度较高，理解和编码难度大。

总结与思考

寻找最长回文子串的方法多样，从暴力搜索到马拉车算法，每种方法都有其优缺点：

1. 暴力搜索法：尽管简单直观，但效率较低，仅适合处理小规模数据。
2. 中心扩展法：通过中心向外扩展，以较高效率找到回文子串，适用于大部分实际应用。
3. 动态规划法：利用子问题记录状态，能有效避免重复计算，但空间复杂度较高。
4. 马拉车算法：在时间复杂度上最优，适用于处理大规模数据的高效需求。

在实际应用中，选择合适的算法不仅依赖于问题的规模和复杂度，还需考虑实现的难易程度和应用场景。

扩展思考

1. 文本处理中的应用：回文子串在自然语言处理、数据压缩等领域有广泛应用，理解回文结构有助于我们更好地处理文本数据。
2. 字符串匹配算法：通过学习最长回文子串的求解方法，我们还能拓展到字符串匹配等更复杂的问题。
3. 时间复杂度优化：马拉车算法为 O(n) 的复杂度，为我们提供了极致优化的思路，值得在其他复杂算法问题中学习和借鉴。

通过本文的讲解，相信你已经对寻找最长回文子串的各种算法有了深入的理解，并掌握了处理类似字符串问题的技巧。