這篇文章要解說的是 LeetCode 題目 5. Longest Palindromic Substring，這是一道典型的字串題，重點在於找出輸入字串中的最長回文子字串。下面是這篇解題教學的詳細分析與多種解法，讓你能全面掌握這題的技巧。
題目概述
給定一個字串 s，我們需要找出其中最長的回文子字串。如果字串是空的，可以直接返回空字串。回文是指正讀與反讀相同的字串。例如，"aba" 和 "racecar" 都是回文。
思路與解法
這道題有多種解法，從基礎到進階，我們可以逐步優化以降低時間複雜度。以下列出三種常見的解法：- 暴力解法 (Brute Force)
- 中心擴展法 (Expand Around Center)
- 動態規劃法 (Dynamic Programming)
解法一：暴力解法 (Brute Force)
這是最直接的方式，透過遍歷所有可能的子字串並檢查每個子字串是否為回文。若是回文，則更新最長回文的紀錄。這樣的解法較為簡單易懂，但時間複雜度較高。
步驟：
- 從頭遍歷字串
s，並考慮所有可能的子字串。 - 檢查每個子字串是否為回文。
- 如果找到的回文子字串比當前記錄的最長回文長，就更新最長回文。
實作 (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)
回文子串具有對稱性，因此可以從每個可能的中心點開始，嘗試向外擴展來找出最長的回文子串。
步驟：
- 從每個位置開始，將它視為回文的中心點。
- 對於每個中心點，從該點向兩側擴展，找到最長的回文。
- 如果擴展得到的回文比目前記錄的最長回文長，則更新最長回文。
注意：回文中心可能是單個字元（奇數長度回文）或兩個字元（偶數長度回文）。
實作 (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)
這是一種進階解法，利用動態規劃表格來儲存回文資訊，以避免重複計算。
步驟：
- 建立一個二維布林陣列
dp，其中dp[i][j]表示字串s[i:j+1]是否為回文。 - 若
s[i] == s[j]且子串s[i+1:j-1]也是回文，則s[i:j+1]也是回文。 - 每當找到較長的回文子串時，就更新最長回文的紀錄。
實作 (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 這道題目！
