最长回文子串
在这里插入图片描述
若一个字符串是回文串，那么它的首尾元素应该相同，并且若该字符串的长度大于2，除去首尾元素后依然是回文串。
由此可得到判断是否是回文串的递推公式， 代表子串
到
是否是回文串：
当且仅当到
是回文串，即
，且
时，
对于所有是回文串的子串，记录其长度，选择最长的
代码如下：
class Solution:
def longestPalindrome(self, s: str) -> str:
# 字符串长度小于2，则整个字符串都是回文串
n = len(s)
if n < 2:
return s
begin = 0
maxlen = 1 # 任意一个元素都是回文串
# 初始化,dp[i][j]表示s[i]...s[j]的子串是否是回文串
dp = [[False]*n for _ in range(n)]
for i in range(n):
dp[i][i] = True
# 任意一个元素s[i]都是回文串
# 递推，遍历所有开始结束位置i,j。并判断是否是回文串
for j in range(1,n):
for i in range(j):
if s[i] != s[j]:
# 首尾元素不相同，肯定不是回文串
dp[i][j] = False
else:
if j-i < 3:
dp[i][j] = True
# 首尾元素相同，剩余部分少于一个元素
else:
dp[i][j] = dp[i+1][j-1]
if dp[i][j] and j - i + 1 > maxlen:
# 记录最长的回文串索引
maxlen = j - i + 1
begin = i
return s[begin:begin+maxlen]
