全国旗舰校区

不同学习城市 同样授课品质

北京

深圳

上海

广州

郑州

大连

武汉

成都

西安

杭州

青岛

重庆

长沙

哈尔滨

南京

太原

沈阳

合肥

贵阳

济南

下一个校区
就在你家门口
+
当前位置:首页  >  技术干货  >  详情

python找回文子串的方法

来源:千锋教育
发布人:xqq
2023-11-14

推荐

在线提问>>

python找回文子串的方法

1、双指针两边扩展

遍历指针为i,j=i+1,i左移,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

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

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学习教程请关注IT培训机构:千锋教育。

相关文章

python中如何实现列表与字典的相互转换?

python sorted中key参数怎么用?

python中exec()函数如何执行表达式?

Python中使用K-means算法

python如何对电脑进行清屏

开班信息 更多>>

课程名称
全部学科
咨询

HTML5大前端

Java分布式开发

Python数据分析

Linux运维+云计算

全栈软件测试

大数据+数据智能

智能物联网+嵌入式

网络安全

全链路UI/UE设计

Unity游戏开发

新媒体短视频直播电商

影视剪辑包装

游戏原画

    在线咨询 免费试学 教程领取