Yoru Karu Studio
Yoru Karu Studio

LeetCode 解題思路：5. Longest Palindromic Substring（最長回文子字串）

從中心擴展到動態規劃的多種解法

luk 收錄於 Leetcode
 約 1200 字 預計閱讀 6 分鐘 

題目描述

給定一個字串 s，找到 s 中最長的回文子字串。

回文（Palindrome）：正著讀和反著讀都一樣的字串，例如 “aba”、“noon”。

範例： 

輸入：s = "babad"
輸出："bab"
解釋："aba" 也是有效答案

輸入：s = "cbbd"
輸出："bb"

輸入：s = "a"
輸出："a"

輸入：s = "ac"
輸出："a" 或 "c"

核心概念理解

什麼是回文？

  • 奇數長度回文：有一個中心字元，如 “aba”（中心是 ‘b’）
  • 偶數長度回文：有兩個中心字元，如 “abba”（中心是 ‘bb’）

回文的性質 

"babad" 中的回文：
- "b" (長度 1)
- "a" (長度 1)
- "bab" (長度 3) ← 以 'a' 為中心
- "aba" (長度 3) ← 以 'b' 為中心
- "d" (長度 1)

最長的是 "bab" 或 "aba"（長度都是 3）

問題關鍵

  1. 需要找到連續的回文子字串（不是子序列）
  2. 返回的是子字串本身，不只是長度
  3. 可能有多個答案，返回任意一個即可

解法一：暴力解法

思路

枚舉所有可能的子字串，檢查是否為回文，記錄最長的。

程式碼 

def longestPalindrome(s):
    def isPalindrome(sub):
        """檢查字串是否為回文"""
        return sub == sub[::-1]

    n = len(s)
    max_len = 0
    result = ""

    # 枚舉所有子字串
    for i in range(n):
        for j in range(i, n):
            substring = s[i:j+1]
            if isPalindrome(substring) and len(substring) > max_len:
                max_len = len(substring)
                result = substring

    return result

複雜度分析

  • 時間複雜度：O(n³)
    • 枚舉子字串：O(n²)
    • 檢查是否回文：O(n)
  • 空間複雜度：O(1)
    • 不考慮切片產生的臨時字串

優缺點

  • ✅ 邏輯簡單
  • ❌ 效率極低，大數據會超時

解法二：中心擴展法（推薦）

思路

回文是對稱的，可以從中心向兩邊擴展：

  1. 枚舉每個可能的中心點
  2. 從中心向兩邊擴展，直到不再是回文
  3. 記錄最長的回文

關鍵：需要考慮奇數和偶數長度兩種情況！

程式碼 

def longestPalindrome(s):
    def expandAroundCenter(left, right):
        """從中心向兩邊擴展，返回回文長度"""
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        # 返回回文長度（注意此時 left 和 right 已經越界）
        return right - left - 1

    if not s:
        return ""

    start = 0  # 最長回文的起始位置
    max_len = 0

    for i in range(len(s)):
        # 情況1：奇數長度回文（中心是一個字元）
        len1 = expandAroundCenter(i, i)

        # 情況2：偶數長度回文（中心是兩個字元）
        len2 = expandAroundCenter(i, i + 1)

        # 取較長的
        current_len = max(len1, len2)

        # 更新最長回文
        if current_len > max_len:
            max_len = current_len
            # 計算起始位置
            start = i - (current_len - 1) // 2

    return s[start:start + max_len]

演算過程示例 

s = "babad"

i=0, s[0]='b':
  奇數中心 (0, 0): "b" → 長度 1
  偶數中心 (0, 1): "ba" 不是回文 → 長度 0
  current_len = 1

i=1, s[1]='a':
  奇數中心 (1, 1):
    s[1]='a' ✓
    s[0]='b', s[2]='b' ✓ → "bab"
    s[-1] 越界，停止
    長度 = 3
  偶數中心 (1, 2): "ab" 不是回文 → 長度 0
  current_len = 3
  更新：max_len=3, start=0

i=2, s[2]='b':
  奇數中心 (2, 2):
    s[2]='b' ✓
    s[1]='a', s[3]='a' ✓ → "aba"
    s[0]='b', s[4]='d' ✗，停止
    長度 = 3
  偶數中心 (2, 3): "ba" 不是回文 → 長度 0
  current_len = 3（不更新，因為不大於 max_len）

繼續... 最終返回 s[0:3] = "bab"

起始位置計算解析 

start = i - (current_len - 1) // 2

範例：i=1, current_len=3（回文是 "bab"）
start = 1 - (3-1)//2 = 1 - 1 = 0 ✓

範例：i=2, current_len=4（回文是 "abba"）
start = 2 - (4-1)//2 = 2 - 1 = 1 ✓

複雜度分析

  • 時間複雜度：O(n²)
    • 枚舉中心點：O(n)
    • 每個中心點最多擴展 n 次：O(n)
  • 空間複雜度：O(1)
    • 只用了幾個變數

解法三：動態規劃

思路

定義 dp[i][j] 表示 s[i:j+1] 是否為回文。

轉移方程：

dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]

邊界條件：

  • 單字元一定是回文：dp[i][i] = True
  • 兩字元相同就是回文：dp[i][i+1] = (s[i] == s[i+1])

程式碼 

def longestPalindrome(s):
    n = len(s)
    if n < 2:
        return s

    # 初始化 DP 表
    dp = [[False] * n for _ in range(n)]

    # 所有單字元都是回文
    for i in range(n):
        dp[i][i] = True

    start = 0
    max_len = 1

    # 按照長度遞增的順序填表
    for length in range(2, n + 1):  # 長度從 2 到 n
        for i in range(n - length + 1):
            j = i + length - 1  # 終點索引

            if s[i] == s[j]:
                # 長度為 2 或內部是回文
                if length == 2 or dp[i + 1][j - 1]:
                    dp[i][j] = True
                    if length > max_len:
                        max_len = length
                        start = i

    return s[start:start + max_len]

DP 表格示例 

s = "babad"

     0   1   2   3   4
     b   a   b   a   d
0 b  T   F   T   F   F
1 a      T   F   T   F
2 b          T   F   F
3 a              T   F
4 d                  T

填表順序（按長度）：
長度1: 對角線全為 T
長度2: dp[0][1]=F, dp[1][2]=F, dp[2][3]=F, dp[3][4]=F
長度3: dp[0][2]=T (bab), dp[1][3]=T (aba), dp[2][4]=F
長度4: dp[0][3]=F, dp[1][4]=F
長度5: dp[0][4]=F

找到的回文：dp[0][2]="bab", dp[1][3]="aba"

複雜度分析

  • 時間複雜度：O(n²)
    • 需要填充 n² 個表格
  • 空間複雜度：O(n²)
    • DP 表格大小為 n×n

解法四：Manacher 演算法（進階）

思路

Manacher 演算法是專門解決回文問題的 O(n) 演算法，但實作較複雜。

核心思想：

  1. 在每個字元間插入特殊字元（如 ‘#’），統一處理奇偶長度
  2. 利用回文的對稱性，避免重複計算

程式碼 

def longestPalindrome(s):
    # 預處理：插入 '#'
    # "babad" → "#b#a#b#a#d#"
    T = '#'.join('^{}$'.format(s))
    n = len(T)
    P = [0] * n  # P[i] 表示以 i 為中心的回文半徑
    center = 0   # 當前最右回文的中心
    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

    return s[start:start + max_len]

複雜度分析

  • 時間複雜度：O(n)
    • 每個位置最多被訪問兩次
  • 空間複雜度：O(n)
    • 需要額外陣列儲存半徑

四種解法比較

解法時間複雜度空間複雜度難度推薦度
暴力解O(n³)O(1)簡單⭐
中心擴展O(n²)O(1)中等⭐⭐⭐⭐⭐
動態規劃O(n²)O(n²)中等⭐⭐⭐
ManacherO(n)O(n)困難⭐⭐

面試推薦：中心擴展法（代碼簡潔，空間優秀，易於理解）

程式碼技巧解析

1. 中心擴展的兩種情況 

# 奇數長度：中心是一個字元
expandAroundCenter(i, i)    # "aba"

# 偶數長度：中心是兩個字元
expandAroundCenter(i, i+1)  # "abba"

2. 擴展後的長度計算 

def expandAroundCenter(left, right):
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    # 此時 left 和 right 已越界
    # 實際回文是 s[left+1 : right]
    return right - left - 1

3. 起始位置的數學推導 

已知：中心位置 i，回文長度 len
求：起始位置 start

奇數情況（如 "aba"，中心 i=1，len=3）：
  start = i - len//2 = 1 - 1 = 0 ✓

偶數情況（如 "abba"，中心在 i=1 和 i=2 之間，len=4）：
  使用 i=1 計算
  start = i - (len-1)//2 = 1 - 1 = 0 ✓

統一公式：start = i - (len-1)//2

4. DP 填表順序 

# 錯誤：從左上到右下
for i in range(n):
    for j in range(i, n):
        # dp[i+1][j-1] 可能還沒計算！

# 正確：按長度遞增
for length in range(2, n + 1):
    for i in range(n - length + 1):
        j = i + length - 1
        # 確保 dp[i+1][j-1] 已經計算過

常見錯誤與注意事項

❌ 錯誤1：忘記處理偶數長度回文 

# 錯誤：只檢查奇數長度
for i in range(len(s)):
    expandAroundCenter(i, i)  # 遺漏 (i, i+1)

❌ 錯誤2：邊界判斷遺漏 

# 錯誤：沒有檢查邊界
while s[left] == s[right]:  # left 可能 < 0，right 可能越界
    left -= 1
    right += 1

❌ 錯誤3：起始位置計算錯誤 

# 錯誤
start = i - current_len // 2  # 應該是 (current_len - 1) // 2

❌ 錯誤4：DP 邊界條件遺漏 

# 錯誤：忘記長度為 2 的特殊情況
if dp[i + 1][j - 1]:  # 當 j = i+1 時，i+1 > j-1，無意義
    dp[i][j] = True

# 正確
if length == 2 or dp[i + 1][j - 1]:
    dp[i][j] = True

延伸思考

1. 只返回長度 

def longestPalindromeLength(s):
    # 中心擴展法只需記錄最大長度
    max_len = 0
    for i in range(len(s)):
        len1 = expandAroundCenter(i, i)
        len2 = expandAroundCenter(i, i + 1)
        max_len = max(max_len, len1, len2)
    return max_len

2. 返回所有最長回文 

def allLongestPalindromes(s):
    max_len = 0
    results = []

    for i in range(len(s)):
        for left, right in [(i, i), (i, i + 1)]:
            l, r = left, right
            while l >= 0 and r < len(s) and s[l] == s[r]:
                l -= 1
                r += 1
            length = r - l - 1
            if length > max_len:
                max_len = length
                results = [s[l + 1:r]]
            elif length == max_len:
                results.append(s[l + 1:r])

    return list(set(results))  # 去重

3. 計算回文子字串總數 

def countPalindromes(s):
    count = 0
    for i in range(len(s)):
        # 奇數長度
        l = r = i
        while l >= 0 and r < len(s) and s[l] == s[r]:
            count += 1
            l -= 1
            r += 1
        # 偶數長度
        l, r = i, i + 1
        while l >= 0 and r < len(s) and s[l] == s[r]:
            count += 1
            l -= 1
            r += 1
    return count

重要觀念總結

  1. 回文的對稱性：

    • 從中心擴展是最自然的思考方式
    • 需要考慮奇數和偶數兩種情況

  2. 中心擴展 vs 動態規劃：

    • 中心擴展：空間 O(1)，代碼簡潔
    • 動態規劃：空間 O(n²)，但思路清晰

  3. 邊界條件處理：

    • 單字元、兩字元的特殊情況
    • 陣列越界的檢查

  4. 優化思路：

    • 利用已知資訊避免重複計算（DP）
    • 利用對稱性減少比較次數（Manacher）

相關題目

  • LeetCode 647: Palindromic Substrings（回文子字串計數）
  • LeetCode 516: Longest Palindromic Subsequence（最長回文子序列）
  • LeetCode 214: Shortest Palindrome（最短回文）
  • LeetCode 131: Palindrome Partitioning（回文分割）
  • LeetCode 680: Valid Palindrome II（驗證回文 II）

練習建議

  1. 先理解回文的定義，手寫幾個例子
  2. 實現中心擴展法，理解奇偶兩種情況
  3. 嘗試動態規劃解法，畫出 DP 表格
  4. 測試邊界情況：單字元、全相同、無回文
  5. 挑戰 Manacher 演算法（選修）

這道題是字串處理和中心擴展思想的經典題目，中心擴展法的思路在很多問題中都會用到，非常值得掌握！

更新於 2025-01-05 
CC BY-NC-SA 4.0
閱讀原始文檔
LeetcodeAlgorithmStringDynamic-Programming
返回 | 主頁
0%