使用LeetCode怎么求最长回文子串

# 使用LeetCode怎么求最长回文子串

## 什么是回文串？

在解决「最长回文子串」问题之前，我们首先需要明确什么是回文串。**回文串（Palindrome）**是指正读和反读都相同的字符串。例如：
- "aba" 是回文串
- "abba" 是回文串
- "abc" 不是回文串

## 问题描述

LeetCode上的[第5题：最长回文子串](https://leetcode.com/problems/longest-palindromic-substring/)题目要求：

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

示例：

输入: “babad” 输出: “bab” 或 “aba”

## 解决思路

### 1. 暴力解法（Brute Force）

**思路**：枚举所有可能的子串，判断是否为回文，记录最长的。

**时间复杂度**：O(n³)（枚举子串O(n²)，判断回文O(n)）

**代码实现**：
```python
def longestPalindrome(s: str) -> str:
    if not s:
        return ""
    
    n = len(s)
    max_len = 1
    start = 0
    
    for i in range(n):
        for j in range(i + 1, n):
            if j - i + 1 > max_len and is_palindrome(s, i, j):
                max_len = j - i + 1
                start = i
    return s[start:start + max_len]

def is_palindrome(s: str, left: int, right: int) -> bool:
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

缺点：时间复杂度太高，无法通过LeetCode的所有测试用例。

2. 动态规划（Dynamic Programming）

思路：利用回文串的性质，如果一个子串是回文串，并且它的左右字符相同，那么扩展后的子串也是回文串。

状态定义：dp[i][j] 表示子串 s[i..j] 是否为回文串。

状态转移方程： - dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1] - 边界条件：当子串长度为1或2时，直接判断 s[i] == s[j]

时间复杂度：O(n²)

空间复杂度：O(n²)

代码实现：

def longestPalindrome(s: str) -> str:
    n = len(s)
    if n < 2:
        return s
    
    dp = [[False] * n for _ in range(n)]
    start = 0
    max_len = 1
    
    # 所有长度为1的子串都是回文
    for i in range(n):
        dp[i][i] = True
    
    # 枚举子串长度
    for length in range(2, n + 1):
        # 枚举左边界
        for i in range(n):
            j = i + length - 1  # 右边界
            if j >= n:
                break
                
            if s[i] != s[j]:
                dp[i][j] = False
            else:
                if length == 2:
                    dp[i][j] = True
                else:
                    dp[i][j] = dp[i + 1][j - 1]
            
            if dp[i][j] and length > max_len:
                max_len = length
                start = i
    return s[start:start + max_len]

3. 中心扩展法（Expand Around Center）

思路：回文串可以从它的中心展开，并且总共有 2n - 1 个可能的中心（包括字符间空隙）。

时间复杂度：O(n²)

空间复杂度：O(1)

代码实现：

def longestPalindrome(s: str) -> str:
    if not s:
        return ""
    
    start = 0
    end = 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]

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

4. Manacher算法（最优解）

思路：利用回文串的对称性，在O(n)时间内解决问题。

时间复杂度：O(n)

空间复杂度：O(n)

代码实现：

def longestPalindrome(s: str) -> str:
    # 预处理字符串
    t = '#'.join('^{}$'.format(s))
    n = len(t)
    p = [0] * n
    center = right = 0
    
    for i in range(1, n - 1):
        # 利用对称性
        if i < right:
            mirror = 2 * center - i
            p[i] = min(right - i, p[mirror])
        
        # 尝试扩展
        while t[i + p[i] + 1] == t[i - p[i] - 1]:
            p[i] += 1
        
        # 更新中心和右边界
        if i + p[i] > right:
            center = i
            right = i + p[i]
    
    # 找到最大回文子串
    max_len = max(p)
    center_index = p.index(max_len)
    start = (center_index - max_len) // 2
    end = start + max_len
    return s[start:end]

性能对比

实际应用中的选择

• 面试场景：推荐使用中心扩展法，代码简洁且易于解释。
• 竞赛场景：可以使用Manacher算法追求最优性能。
• 学习目的：建议从暴力解法开始，逐步优化到动态规划和中心扩展法。

总结

求解最长回文子串是一个经典的字符串处理问题，本文介绍了四种解法： 1. 暴力解法（理解基础） 2. 动态规划（空间换时间） 3. 中心扩展法（实际常用） 4. Manacher算法（最优解）

在LeetCode上提交时，中心扩展法通常是性价比最高的选择，能够在合理的时间内通过所有测试用例。对于特别长的字符串（如长度>10⁵），则应该考虑Manacher算法。

通过这个问题，我们不仅学习了回文串的处理技巧，还体会到了算法优化的重要性——从O(n³)到O(n)的飞跃，正是算法之美所在。 “`

这篇文章共计约1800字，完整涵盖了从基础到优化的解决方案，并包含代码实现和复杂度分析。