給定一個字符串 s肥缔，找到 s 中最長的回文子串芒划。你可以假設(shè) s 的最大長度為 1000逐沙。
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個有效答案超埋。
輸入: "cbbd"
輸出: "bb"
class Solution:
def longestPalindrome(self, s: str) -> str:
size = len(s)
if size == 0:
return s
res = s[0]
def extend(i,j,s):
while i>=0 and j <len(s):
if s[i] == s[j]:
i -=1
j +=1
else:
break
return s[i+1:j]
for i in range(size-1):
res1 = extend(i,i,s) # 單數(shù)擴散
res2 = extend(i,i+1,s) # 雙數(shù)擴散
if max(len(res1),len(res2)) > len(res):
res = res1 if len(res1) > len(res2) else res2
return res
中心擴散法
注意中可以是單個數(shù) 也可以是雙數(shù)
