给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
思路：动态规划，
dp[i][j] 记录 s[i:j] 是不是一个回文串,判断回文串满足以下2个条件
- s[i] = s[j]
- s[i+1:j-1] 是一个回文串,这里用一个条件判断 i+1 >= j-1, 初始化 长度为1 和 长度为0 的串为回文串
class Solution:
def longestPalindrome(self, s: str) -> str:
if not s:
return s
dp = [[0 for _ in range(len(s))] for __ in range(len(s))]
ans = s[0]
for substr_len in range(1,len(s)+1):
for i in range(len(s)-substr_len+1):
if substr - len(ans)>2:
break
#print(substr_len,i)
if substr_len == 1:
dp[i][i] = 1
elif substr_len == 2 and s[i] == s[i+1]:
dp[i][i+1] = 1
ans = s[i:i+substr_len]
else:
if dp[i+1][i+substr_len-2] == 1 and s[i] == s[i+substr_len-1]:
dp[i][i+substr_len-1] = 1
ans = s[i:i+substr_len]
return ans
class Solution:
def longestPalindrome(self, s: str) -> str:
if not s:
return s
dp = [[0 for _ in range(len(s))] for __ in range(len(s))]
max_substr_len = 0
for substr_len in range(1,len(s)+1):
if substr_len - max_substr_len >2:
break
for i in range(len(s)-substr_len+1):
#print(substr_len,i)
if substr_len == 1:
dp[i][i] = 1
ans = s[i:i+substr_len]
max_substr_len = substr_len
elif substr_len == 2 and s[i] == s[i+1]:
dp[i][i+1] = 1
ans = s[i:i+substr_len]
max_substr_len = substr_len
else:
if s[i] != s[i+substr_len-1]:
continue
elif dp[i+1][i+substr_len-2] == 1 :
dp[i][i+substr_len-1] = 1
ans = s[i:i+substr_len]
max_substr_len = substr_len
return ans