[Python][Leetcode]中心擴展法 (Expand Around Center)

5. Longest Palindromic Substring

這個問題是要求你在一個給定的字串 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)。

核心思路

回文的特性是它對稱於中心點。中心點可以是：

1. 單個字元 (適用於奇數長度的回文，如 aba，中心是b。
2. 兩個字元之間的空隙 (適用於偶數長度的回文，如abbas，中心在兩bb之間)。

中心擴展法就是遍歷字串 s 中的所有可能的 2N - 1個中心點，並從該中心點向兩側擴展，直到不再是回文為止，記錄下最長的回文子字串。

步驟

1. 遍歷字串 s將每個索引 i 視為可能的奇數長度回文的中心點。
2. 同時，將每對相鄰索引 (i, i+1)視為可能的偶數長度回文的中心點。
3. 定義一個輔助函數 expand(left, right)，它接收左右兩個索引，並不斷向外擴展，直到 s[left]不等於s[right]或超出邊界，然後返回找到的回文子字串。
4. 在每次擴展後，比較找到的回文長度與目前記錄的最長回文，並進行更新。

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