5. 最長(zhǎng)回文子串

給定一個(gè)字符串 s，找到 s 中最長(zhǎng)的回文子串。你可以假設(shè) s 的最大長(zhǎng)度為 1000。

示例 1：
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個(gè)有效答案。

示例 2：
輸入: "cbbd"
輸出: "bb"

思路:

1. 采用動(dòng)態(tài)規(guī)劃的思想
   • 要知道s[i]和s[j]之間的字符是否為回文字符, 我們只需知道s[i] ==s[j] 并且 s[i+1:j-1]為回文字符串
2. 創(chuàng)建N * N的列表記錄:s[i]到s[j]是否為回文字符
3. 求解順序: 從i = 0, j = 0開(kāi)始記錄, 直到i和j重合, 而后j+=1, i=0, 直到最后j = len(s)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if s is '': return ''
        N = len(s)

        lst=[[False if i != j else True for i in range(N)] for j in range(N)]
        longest = (0, 0)
        i = 0
        j = 0
        while j < N:
            if i == j:
                i = 0
                j = j+1
                continue
            if s[i] == s[j]:
                if j-i == 1 or lst[i+1][j-1] is True:
                    lst[i][j] = True
                    if j - i > longest[1] - longest[0]:
                        longest = i,j 
            i+=1
        return s[longest[0]:longest[1]+1]