Python找回文子串的方法-图灵python

1、双指针两侧扩展

遍历指针为i， j=i+1，我向左移动，j向右移动。判断长度是否相等，下标给临时变量，最后切片返回。唯一的坑。回文字符串的长度可以是奇数或偶数。奇数时，内循环从i-1开始。边界条件也需要处理。

classSolution(object):

deflongestPalindrome(self,s):
"""
:types:str
:rtype:str
"""
n=len(s)
maxL,maxR,max=0,0,0
foriinrange(n):
#回文字符串的长度为偶数
start=i
end=i+1
whilestart>=0andend<n:
ifs[start]==s[end]:
ifend-start+1>max:
max=end-start+1
maxL=start
maxR=end
start-=1
end+=1
else:
break

#长度为奇数的回文子串
start=i-1
end=i+1
whilestart>=0andend<n:
ifs[start]==s[end]:
ifend-start+1>max:
max=end-start+1
maxL=start
maxR=end
start-=1
end+=1
else:
break
returns[maxL:maxR+1]

2、Manacher算法

因为在输入预处理步骤中，所有回文子字符都转换为奇数长度。因此，在以下操作中，只需将输入的每个字符作为回文子字符的中心位置即可。不需要考虑偶数长度的回文子字符。

'''
@author:YizhouZhao
'''
#设置radius[i]=1,因为字符本身也是一个回文数
radius[i]=1
while(string[i-radius[i]]==string[i+radius[i]]):
radius[i]+=1

以上是Python找到文子串的方法，希望对大家有所帮助。更多Python学习指导：python基础教程

本文教程操作环境：windows7系统Python 3.9.1，DELL G3电脑。