使用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(n3)（枚舉子串O(n2)，判斷回文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(n2)

空間復雜度：O(n2)

代碼實現：

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(n2)

空間復雜度：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(n3)到O(n)的飛躍，正是算法之美所在。 “`

這篇文章共計約1800字，完整涵蓋了從基礎到優化的解決方案，并包含代碼實現和復雜度分析。