題目說明

palindromic substring : 回文字串，也就是 reverse 後會與原本字串一樣
題目給定一個字串，找出在這個字串中出現的最長回文字串

解題思路

Approach 1. Brute Force
以每個字元為中心，往兩邊擴展，比較兩邊的字元是否相同

Approach 2. Manacher

X  X  X  {X  X  X  X  X  X  X  X  X  X  X}  X  X  X  X  X
      ---------------
             j          ctr          i

1. 求出 p[i]：p[i] 為 s[i] 為中心的最長回文字符串半徑
2. 迭代過程中，更新 maxCenter 與 maxRight
3. 偶數的字符串，只需為字串加工
   例如：cbabsd => #c#b#a#b#s#d#

程式碼

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # Approach 1 :從第一個元素開始找，向左向右往外伸，如果左右的數字一樣就繼續往下找
        
        # Approach 2 : ManaChar

        # step 1: 多放一個元素，讓結果無論是奇數長度還是偶數長度都可以用同一套解法
        t = "#"
        for c in s:
            t += c
            t += "#"
        # step 2: 宣告 p 陣列 用來裝每個元素為中心的最長字符串
        p = []
        max_center = -1
        max_right = -1
        for i in range(len(t)):
            # 如果遇到接近結尾的字串，其到最後一個字元的長度已經比當前字元更小了，那後面的字元也不用看下去了
            if len(t)- 1 - i < max_right - max_center:
                break

            if i > max_right: # i 超出目前最大字符串的範圍，就只能照原本的走法
                k = 0
                while i-k >= 0 and i+k < len(t) and t[i-k] == t[i+k]:
                    k+=1
            else:
                j = max_center * 2 - i
                k = min(p[j], max_right - i)
                while i-k >= 0 and i+k < len(t) and t[i-k] == t[i+k]:
                    k+=1
            p.append(k-1)
            if k-1 > max_right:

                max_center = i
                max_right = k-1

        # 還原回原本的字符串長度
        max_len, center = max_right, max_center
        
        return s[max_center//2 - max_right//2: max_center//2 - max_right//2 + max_right]
                

其他討論

同樣的解法，用 c++ 無論是 時間還是空間都相當有效，但是用 python 執行卻挺慘的，可以多看一些討論理解 python 比較快的解法

更新紀錄

最後更新日期：2023-07-27

參考資料

1. Huifeng Guan(2021-08-16)。【每日一题】LeetCode 5. Longest Palindromic Substring, 8/27/2021。摘自 Youtube (2023-09-19)