5. Longest Palindromic Substring
Given a string s, return the longest palindromic substring in s.
Example 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd"
Output: "bb"
核心概念解釋
這個問題涉及到三個主要概念：子字串 (Substring)、回文 (Palindrome) 和最長 (Longest)。
- 1. 子字串 (Substring)
- 一個子字串是從原字串中連續取出的一段字元。
- 例如： 在字串 "banana" 中，"ban"、"ana"、"nana" 都是子字串。而 "bna" 就不是，因為字元不是連續的。
- 2. 回文 (Palindrome)
- 一個回文字串是指一個正著讀和反著讀都一樣的字串。
- 例如： "aba"、"racecar"、"madam"、"bb" 都是回文。
- 3. 最長 (Longest)
- 指在所有是回文的子字串中，長度最大的那一個。
對於尋找最長回文子字串（Longest Palindromic Substring）這個經典問題，確實有比暴力解法 (Brute Force, O(N^3) 或 O(N^2)) 更好的解法。
最常見且效率較高的兩種解法是：中心擴展法 (Expand Around Center) 和 動態規劃 (Dynamic Programming, DP)。其中，中心擴展法是最直覺且容易實現的。
暴力解法
找過所有的可能性，來判斷。
class Solution:
def longestPalindrome(self, s: str) -> str:
# 暴力解法思路：
max_len = 0
longest_str = ""
# 1. 檢查所有可能的起點 i
for i in range(len(s)):
# 2. 檢查所有可能的終點 j (j >= i)
for j in range(i, len(s)):
# 3. 取得子字串
substring = s[i:j+1]
# 4. 判斷是否為回文
if substring == substring[::-1]:
# 5. 檢查是否最長
if len(substring) > max_len:
max_len = len(substring)
longest_str = substring
return longest_str
最佳解法一：中心擴展法 (Expand Around Center)
這是解決此問題最常用的方法之一，時間複雜度為 O(N^2)，空間複雜度為 O(1)。
核心思路
回文的特性是它對稱於中心點。中心點可以是：
- 單個字元 (適用於奇數長度的回文，如 aba，中心是b。
- 兩個字元之間的空隙 (適用於偶數長度的回文，如abbas，中心在兩bb之間)。
中心擴展法就是遍歷字串 s 中的所有可能的 2N - 1個中心點，並從該中心點向兩側擴展，直到不再是回文為止，記錄下最長的回文子字串。
步驟
- 遍歷字串 s將每個索引 i 視為可能的奇數長度回文的中心點。
- 同時，將每對相鄰索引
(i, i+1)視為可能的偶數長度回文的中心點。 - 定義一個輔助函數
expand(left, right)，它接收左右兩個索引，並不斷向外擴展，直到s[left]不等於s[right]或超出邊界，然後返回找到的回文子字串。 - 在每次擴展後，比較找到的回文長度與目前記錄的最長回文，並進行更新。
class Solution:
def longestPalindrome(self, s: str) -> str:
# 輔助函數：從中心點向外擴展，找出最長的回文
def expand_around_center(left: int, right: int) -> str:
# 當兩側索引仍在字串範圍內，且字元相同，就持續擴展
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
# 迴圈結束時，(left, right) 已經超出回文邊界
# 所以真正的回文是從 left + 1 到 right - 1 (不包含 right)
return s[left + 1:right]
longest = ""
for i in range(len(s)):
# 1. 處理奇數長度的回文 (中心點為 s[i]，例如 'aba')
palindrome1 = expand_around_center(i, i)
if len(palindrome1) > len(longest):
longest = palindrome1
# 2. 處理偶數長度的回文 (中心點在 s[i] 和 s[i+1] 之間，例如 'abba')
palindrome2 = expand_around_center(i, i + 1)
if len(palindrome2) > len(longest):
longest = palindrome2
return longest
輸入 s = "racecarbabadracecar"
找出最長的回文 racecar
