【说站】Python找回文子串的方法
Python找回文子串的方法
1、双指针两边扩展
遍历指针为i， j=i+1， i左移，j右移。判断是否相等将长度，下标赋给临时变量，最后切片返回。唯一的大坑。回文字符串长度可以是奇数也可以是偶数。奇数的时候，内层循环从i-1开始。边界条件也需要处理好。
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
n = len(s)
maxL, maxR, max = 0, 0, 0
for i in range(n):
# 长度为偶数的回文字符串
start = i
end = i + 1
while start >= 0 and end < n:
if s[start] == s[end]:
if end - start + 1 > max:
max = end - start + 1
maxL = start
maxR = end
start -= 1
end += 1
else:
break
# 长度为奇数的回文子串
start = i - 1
end = i + 1
while start >= 0 and end < n:
if s[start] == s[end]:
if end - start + 1 > max:
max = end - start + 1
maxL = start
maxR = end
start -= 1
end += 1
else:
break
return s[maxL:maxR+1]2、Manacher算法
由于在输入预处理的步骤中，将所有的回文子字符已经转为奇数长度。所以在下面的操作中，只需要将输入的每一个字符，都当做一个回文子字符的中心位即可。不需要考虑偶数长度的回文子字符。
'''
@author: Yizhou Zhao
'''
# 设置 radius[i] = 1, 因为字符本身也是一个回文数
radius[i] = 1
while(string[i-radius[i]] == string[i+radius[i]]):
radius[i] += 1以上就是Python找回文子串的方法，希望对大家有所帮助。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
