5. 最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
思路:
- 采用动态规划的思想
- 要知道s[i]和s[j]之间的字符是否为回文字符, 我们只需知道s[i] ==s[j] 并且 s[i+1:j-1]为回文字符串
- 创建N * N的列表记录:s[i]到s[j]是否为回文字符
- 求解顺序: 从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]
