[LeetCode解題攻略] 5. Longest Palindromic Substring

這篇文章要解說的是 LeetCode 題目 5. Longest Palindromic Substring，這是一道典型的字串題，重點在於找出輸入字串中的最長回文子字串。下面是這篇解題教學的詳細分析與多種解法，讓你能全面掌握這題的技巧。

題目概述

給定一個字串 s，我們需要找出其中最長的回文子字串。如果字串是空的，可以直接返回空字串。回文是指正讀與反讀相同的字串。例如，"aba" 和 "racecar" 都是回文。

思路與解法

這道題有多種解法，從基礎到進階，我們可以逐步優化以降低時間複雜度。以下列出三種常見的解法：

1. 暴力解法 (Brute Force)
2. 中心擴展法 (Expand Around Center)
3. 動態規劃法 (Dynamic Programming)

解法一：暴力解法 (Brute Force)

這是最直接的方式，透過遍歷所有可能的子字串並檢查每個子字串是否為回文。若是回文，則更新最長回文的紀錄。這樣的解法較為簡單易懂，但時間複雜度較高。

步驟：

1. 從頭遍歷字串 s，並考慮所有可能的子字串。
2. 檢查每個子字串是否為回文。
3. 如果找到的回文子字串比當前記錄的最長回文長，就更新最長回文。

實作 (Python)：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        longest = ""
        for i in range(0, len(s)):
            for j in range(i, len(s)):
                substring = s[i:j + 1]
                if (substring == substring[::-1]) and (len(substring) > len(longest)):
                    longest = substring
        return longest

複雜度分析：

• 時間複雜度：O(n^3)（因為有兩層迴圈加上判斷回文的額外操作）
• 空間複雜度：O(1)

暴力解法的時間複雜度過高，因此僅適用於較短的字串。接下來介紹更高效的解法。

解法二：中心擴展法 (Expand Around Center)

回文子串具有對稱性，因此可以從每個可能的中心點開始，嘗試向外擴展來找出最長的回文子串。

步驟：

1. 從每個位置開始，將它視為回文的中心點。
2. 對於每個中心點，從該點向兩側擴展，找到最長的回文。
3. 如果擴展得到的回文比目前記錄的最長回文長，則更新最長回文。

注意：回文中心可能是單個字元（奇數長度回文）或兩個字元（偶數長度回文）。

實作 (Python)：

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

        longest = ""
        for i in range(0, len(s)):
            # 奇數長度的回文
            odd_palindrome = expand_around_center(s, i, i)
            # 偶數長度的回文
            even_palindrome = expand_around_center(s, i, i + 1)
            
            # 更新最長回文
            longest = max(longest, odd_palindrome, even_palindrome, key=len)
        
        return longest

複雜度分析：

• 時間複雜度：O(n^2)（擴展操作最壞情況下需要 O(n)，每次擴展的操作有 O(n) 個中心）
• 空間複雜度：O(1)

中心擴展法已經能夠處理長度較大的字串，且效果不錯。接著，我們會討論時間複雜度更優化的解法。

解法三：動態規劃法 (Dynamic Programming)

這是一種進階解法，利用動態規劃表格來儲存回文資訊，以避免重複計算。

步驟：

1. 建立一個二維布林陣列 dp，其中 dp[i][j] 表示字串 s[i:j+1] 是否為回文。
2. 若 s[i] == s[j] 且子串 s[i+1:j-1] 也是回文，則 s[i:j+1] 也是回文。
3. 每當找到較長的回文子串時，就更新最長回文的紀錄。

實作 (Python)：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n == 0:
            return ""
        
        dp = [[False] * n for _ in range(n)]
        start, max_length = 0, 1
        
        for i in range(n):
            dp[i][i] = True
        
        for length in range(2, n + 1):  # length of the substring
            for i in range(n - length + 1):
                j = i + length - 1
                if s[i] == s[j]:
                    if length == 2 or dp[i + 1][j - 1]:
                        dp[i][j] = True
                        if length > max_length:
                            start, max_length = i, length
        
        return s[start:start + max_length]

複雜度分析：

• 時間複雜度：O(n^2)
• 空間複雜度：O(n^2)（需要存儲所有子串的狀態）

動態規劃法雖然空間複雜度較高，但在實際操作中，對於長字串其效率表現良好，特別是在需要找出所有回文子字串的情況下。

結語

在處理這類字串問題時，不同解法各有其適用的場景。以下是三種解法的適用情境：

• 暴力解法：適合入門理解，僅適用於小規模的輸入。
• 中心擴展法：大多數場景下的理想解法，性能和代碼簡潔性都很好。
• 動態規劃法：適合更大的數據規模，並適用於需要判斷多個回文子串的情境。

希望這篇解題教學能幫助你更好地掌握 Longest Palindromic Substring 這道題目！