这是力扣第五题,根据给定的一个字符串 s,找到 s 中最长的回文子串。如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。回文数字长度可以是奇数个也可以是偶数个。
示例 1:
输入:s = "babad" 输出:"bab"
解释:"aba" 同样是符合题意的答案。
示例 2:
输入:s = "cbbd" 输出:"bb"
解题思路:
使用中心扩散法遍历每个元素,判断其左右两侧是否对称(即是否为回文)。需考虑回文长度为奇数和偶数两种情况。如果较大的父字符串是回文,其子串也一定是回文。记录下每个回文子串的起始和结束位置,注意处理边界情况。最后根据这些位置获取并输出所有回文子串。
代码如下:
class Solution:
def longestPalindrome(self, s: str) -> str:
if not s:
return ""
n = len(s)
start, max_length = 0, 0
for i in range(n):
# 以当前字符为中心的奇数长度回文子串,b-->cbc-->acbca
left, right = i, i
# 判断是否为回文
while left >= 0 and right < n and s[left] == s[right]:
# 如果长度 > max_length 则更新 max_length
if right - left + 1 > max_length:
start = left
max_length = right - left + 1
left -= 1
right += 1
# 以当前字符和下一个字符之间为中心的偶数长度回文子串 bb-->cbbc-->acbbca
left, right = i, i + 1
while left >= 0 and right < n and s[left] == s[right]:
if right - left + 1 > max_length:
start = left
max_length = right - left + 1
left -= 1
right += 1
return s[start:start + max_length]
本文分享自 pythonista的日常 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!