(1) 暴力求解
class Solution:
def longestPalindrome(self, s: str) -> str:
maxlen=0
result=''
for i in range(len(s)):
for j in range(i,len(s)+1):##注意首尾坐标
if s[i:j]==s[i:j][::-1]:
if j-i>maxlen:
maxlen=j-i
result=s[i:j]
#print(result)
return result
（2）动态规划，改进（1）
class Solution:
def longestPalindrome(self, s: str) -> str:
n=len(s)
arr=[[0]*n for i in range(n)]
maxlen=0
result=''
for j in range(n):
for i in range(j+1):
if (j-i<2 or arr[i+1][j-1]==1) and s[i]==s[j]:
arr[i][j]=1
if arr[i][j] and j-i+1>maxlen:
maxlen=j-i+1
result=s[i:j+1]
return result
3. 找到回文串的中心，然后向两边扩展即可。
中心位置我们要奇偶分开考虑，如果字符串长度是奇数的话，中心就只有一个元素；如果字符串是偶数的话，那么中心是两个元素。
class Solution:
def longestPalindrome(self, s: str) -> str:
n=len(s)
def expandAroundCenter(left, right):
L,R=left,right
while L>=0 and R<len(s) and s[L]==s[R]:
L+=-1
R+=1
return R-L-1
maxlen=0
result=''
for i in range(n):
len1=expandAroundCenter(i,i)#中间是奇数
len2=expandAroundCenter(i,i+1)#中间是偶数
mlen=max(len1,len2)
if mlen>maxlen:
maxlen=mlen
result=s[i-(maxlen-1)//2:i+maxlen//2+1]
return result
4. 先确定回文串的右边界i，然后以右边界i向左找回文串。假设在i之前的最长回文子串长度是l，此时我们需要分别检查i+1左侧字符串长度为l+2和l+1子串是不是回文串。如果l+2是回文串，那么字符串的最大长度变成l+2，对于l+1同理。
class Solution:
def longestPalindrome(self, s: str) -> str:
n=len(s)
if (len(s)<2) or s==s[::-1]:
return s
maxlen=1
left=0
for i in range(1,len(s)):
s2=s[i-maxlen-1:i+1] #check L+2
s1=s[i-maxlen:i+1] #check L+1
if i-maxlen-1>=0 and s2==s2[::-1]:
left=i-maxlen-1
maxlen+=2
elif i-maxlen>=0 and s1==s1[::-1]:
left=i-maxlen
maxlen+=1
return s[left:left+maxlen]