最长回文字符串
方法一：暴力匹配 （Brute Force）
1、根据回文子串的定义，枚举所有长度大于等于 22 的子串，依次判断它们是否是回文；
2、在具体实现时，可以只针对大于“当前得到的最长回文子串长度”的子串进行“回文验证”；
3、在记录最长回文子串的时候，可以只记录“当前子串的起始位置”和“子串长度”，不必做截取。这一步我们放在后面的方法中实现。
class Solution:
def longestPalindrome(self, s):
res = []
for i in range(len(s)):
for j in range(i+1,len(s)+1):
if s[i:j] == s[i:j][::-1]:
res.append(s[i:j])
else:
continue
print(res)
return max(res,key=len) #学习这种直接返回列表长度最长的字符串方法
方法二：动态规划
依然从回文串的定义展开讨论：
1、如果一个字符串的头尾两个字符都不相等，那么这个字符串一定不是回文串；
2、如果一个字符串的头尾两个字符相等，才有必要继续判断下去。
（1）如果里面的子串是回文，整体就是回文串；
（2）如果里面的子串不是回文串，整体就不是回文串。
即在头尾字符相等的情况下，里面子串的回文性质据定了整个子串的回文性质，这就是状态转移。因此可以把“状态”定义为原字符串的一个子串是否为回文子串。
第 1 步：定义状态
dp[i][j] 表示子串 s[i, j] 是否为回文子串。
第 2 步：思考状态转移方程
这一步在做分类讨论（根据头尾字符是否相等），根据上面的分析得到：
dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]
第 3 步：考虑初始化
初始化的时候，单个字符一定是回文串，因此把对角线先初始化为 1，即 dp[i][i] = 1 。
第 4 步：考虑输出
只要一得到 dp[i][j] = true，就记录子串的长度和起始位置，没有必要截取，因为截取字符串也要消耗性能，记录此时的回文子串的“起始位置”和“回文长度”即可。
class Solution:
def longestPalindrome(self, s: str) -> str:
size = len(s)
if size < 2:
return s
dp = [[False for _ in range(size)] for _ in range(size)]
max_len = 1
start = 0
for i in range(size):
dp[i][i] = True
for j in range(1, size):
for i in range(0, j):
if s[i] == s[j]:
if j - i < 3:
dp[i][j] = True
else:
dp[i][j] = dp[i + 1][j - 1]
else:
dp[i][j] = False
if dp[i][j]:
cur_len = j - i + 1
if cur_len > max_len:
max_len = cur_len
start = i
return s[start:start + max_len]
class Solution2:
def longestPalindrome(self, s):
if not s:
return ""
s_len = len(s)
mem = [[0] * s_len for _ in range(s_len)]
left, right, result_len = 0, 0, 0
for j in range(s_len):
for i in range(0,j):
if s[i] == s[j] and (j - i < 2 or mem[i + 1][j - 1]): # if 0 or other -->(0为False)
mem[i][j] = 1
if mem[i][j] and result_len < j - i + 1:
result_len = j - i + 1
left, right = i, j
mem[j][j] = 1
print(mem)
return s[left:right + 1]