05.最长回文子串

1. 思路：动态规划,一个回文串的头尾应该相等，且去掉头尾之后依然是回文串。
2. dp[i][j]表示下标从i到j的连续子串是否为回文串
3. 当s[i]==s[j]时，也就是子串头尾相等时，如果去掉子串的头尾得到的子串是回文串，则子串为回文串，因此当L=j-i+1>3时，dp[i][j] = dp[i+1][j-1];L<3(即L=2)时，dp[i][j]=True。
4. 当s[i]!=s[j]时，dp[i][j]=False。
5. 对每一个dp[i][j],若为True,判断L是否大于最大长度，如果是，更新最大长度，并记录子串的起始位置i。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        '''
        #暴力解法,用例152会超时
        if len(s) < 2:
            return s
        maxlen = 1
        maxsub = s[0]
        for i in range(len(s)-1):
            for j in range(i+1,len(s)):
                sub = s[i:j+1]
                if sub == sub[::-1] and len(sub) > maxlen:
                    maxlen = len(sub)
                    maxsub = sub
        return maxsub
        '''
        #动态规划
        n = len(s)
        if n < 2:
            return s
        maxlen = 1
        begin = 0
        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):
                j = i+L-1
                if j >= n:
                    break
                if s[i] != s[j]:
                    dp[i][j] = False
                else:
                    if L < 3:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i+1][j-1]
                if dp[i][j] and L > maxlen:
                    maxlen = L
                    begin = i
        return s[begin:begin+maxlen]