【中心拓展法-BM73 最长回文子串】
题目
BM73 最长回文子串
分析
中心拓展法:
中心有两种:
- 将字母作为中心(start=i,end = i),
- 将字母后的间隙作为中心(start = i, end = i+1)
此时要注意begin 和end之间字母数量的计算:
begin 和end 之间的字母数量应为 end-begin+1 但是跳出while循环时,s[begin]!=s[end],所以要begin-1,end-1后再计算两者之间的字母数量
时间复杂度O(n*n)
代码
class Solution:
# write code here
def ans(self, s:str, begin:int, end:int)->int:
if s[begin] != s[end] :
return 0
while(begin>=0 and end <len(s) and s[begin]==s[end]):
begin -= 1
end += 1
# begin 和end 之间的字母数量应为 end-begin+1 但是跳出while循环时,s[begin]!=s[end],所以要begin-1,end-1后再计算两者之间的字母数量
return end-begin-1
def getLongestPalindrome(self , A: str) -> int:
res = 1
for i in range(len(A)-1):
res = max(res, self.ans(A,i,i), self.ans(A,i,i+1))
return res