Python找回文子串的方法
- 更新时间:2021-07-03 09:18:38
- 编辑:符晨希
给网友们整理相关的编程文章,网友师莹莹根据主题投稿了本篇教程内容,涉及到Python相关内容,已被802网友关注,如果对知识点想更进一步了解可以在下方电子资料中获取。
参考资料
- 《中学生Python创意编程》源码课件 配套资源 / 593 MB / 方其桂 推荐度:
- 数据科学实战手册(R+Python) PDF 电子书 / 58.7 MB / Tony Ojeda(托尼·奥杰德) 推荐度:
- 《Python数据分析实战》源码 配套资源 / 1.59 MB / 伊凡?伊德里斯 推荐度:
- 《Python程序设计(第3版)》教学PPT 配套资源 / 5 MB / [美] 约翰·策勒 (John Zell 推荐度:
- 《Python金融数据分析》源码 配套资源 / 3.4 MB / 马伟明 推荐度:
正文内容
为学习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找回文子串的方法,希望对大家有所帮助。
本文教程操作环境:windows7系统、Python 3.9.1,DELL G3电脑。
相关教程
-
Python3.6基于正则实现的计算器示例【无优化简单注释版】
这篇文章主要介绍了Python3.6基于正则实现的计算器,涉及Python基于正则表达式的算术式遍历、查找及数学运算相关操作技巧,需要的朋友可以参考下
发布时间:2019-08-26
-
Python中random模块常用方法的使用教程
这篇文章主要给大家介绍了关于Python中random模块常用方法的使用教程,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
发布时间:2021-05-02