LeetCode刷題筆記第5題：最長回文子串

想法：

求解一個字元串中的最長回文子串使用動态規劃的方法。動态規劃方法是将每個符合回文串的存儲下來，并最終判斷回文串的長度來獲得最長回文串，具體解析如下代碼。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        # 長度小于2的字元串中最多隻有一個字元，傳回自身
        if n < 2:
            return s
        
        max_len = 1
        begin = 0
        # dp[i][j] 表示 s[i..j] 是否是回文串
        # 建立一個n行，n列的數組為後續存放對應位置是否為回文串做準備
        dp = [[False] * n for _ in range(n)]
        # 将對角線上是對自身的比較，一定是為真
        for i in range(n):
            dp[i][i] = True
        
        # 遞推開始
        # 先枚舉子串長度
        # 由于較大子串的判斷依賴前面較小子串的結果，也就是在數組中該位置左下方的結果，應該先從左到右判斷較小子串是否為回文串
        # 設定左右兩個邊界，邊界之間長度小于三時，隻有最中間一個元素，此時不需要再判斷
        for L in range(2, n + 1):
            # 枚舉左邊界，左邊界的上限設定可以寬松一些
            for i in range(n):
                # 由 L 和 i 可以确定右邊界，即 j - i + 1 = L 得
                j = L + i - 1
                # 如果右邊界越界，就可以退出目前循環
                if j >= n:
                    break

                # 此時兩個位置上的字元不同，則對應數組中存儲為False，即為此處不是回文串    
                if s[i] != s[j]:
                    dp[i][j] = False 
                else:
                    # 當距離小于3時它們之間僅有一個元素不需要再判斷，此時為回文串，存儲True
                    if j - i < 3:
                        dp[i][j] = True
                    # 當距離大于等于3時還需要對兩端進行位移并繼續判斷
                    else:
                        dp[i][j] = dp[i + 1][j - 1]
                
                # 隻要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此時記錄回文長度和起始位置
                # 獲得長度最長的子串，并獲得相對應的開始于結束的位置
                if dp[i][j] and j - i + 1 > max_len:
                    max_len = j - i + 1
                    begin = i
        
        # 傳回相應位置的字元串
        return s[begin:begin + max_len]