LeetCode每日一题: 5. 最长回文子串

5. 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

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

思路:

1. 采用动态规划的思想
   • 要知道s[i]和s[j]之间的字符是否为回文字符, 我们只需知道s[i] ==s[j] 并且 s[i+1:j-1]为回文字符串
2. 创建N * N的列表记录:s[i]到s[j]是否为回文字符
3. 求解顺序: 从i = 0, j = 0开始记录, 直到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]