一天一道LeetCode(三)5. 最长回文子串
5. 最长回文子串
题目描述:
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1:
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2:
输入: "cbbd"
输出: "bb"
解题思路:
依次遍历从中心扩展,可能有“aba“型,也可能是”bb“型
class Solution:
def longestPalindrome(self, s: str) -> str:
if len(s) < 2 or s == s[::-1]:
return s
maxlen = 0
left = 0
right = 0
for i in range(1,len(s)):
k = 1
while(i - k >= 0 and i + k <len(s)):
if s[i - k] == s[i + k]:
if k*2 + 1 > maxlen:
maxlen = k * 2 + 1
left = i - k
right = i + k
k += 1
else:
break
k = 1
while(i - k >= 0 and i + k - 1 <len(s)):
if s[i - k] == s[i + k - 1]:
if k * 2 > maxlen:
maxlen = k * 2
left = i - k
right = i + k - 1
k += 1
else:
break
return s[left:right+1]
有特别坑的测例,像"aaaaaaaaaaaaaaaaaaaaaaa"这种
不加前面特殊判断:
加了特殊判断: