【说站】Python找回文子串的方法
2024-10-17
49
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找回文子串的方法,希望对大家有所帮助。更多Python学习指路:python基础教程
本文教程操作环境:windows7系统、Python 3.9.1,DELL G3电脑。
更新于:26天前赞一波!
相关文章
- 【说站】java8中的四种方法引用
- 【说站】python如何追写内容
- 【说站】python的浮点数占多少个字节
- 【说站】python反向输出数字
- 【说站】python中__file__属性的使用
- 【说站】python输入三个数求平均值
- 【说站】python提取字符串指定内容
- 【说站】python将数字转化为汉字
- 【说站】python快捷键
- 【说站】python交换两个变量的值
- 【说站】python截取字符串中特定部分
- 【说站】python统计不同字符的个数
- 【说站】python三元操作符如何赋值
- 【说站】python使用字节处理文件
- 【说站】python类变量和实例变量的对比
- 【说站】python关闭文件的两种方法
- 【说站】python缓冲二进制文件
- 【说站】python怎么导入pygame模块
- 【说站】python文件路径的组成
- 【说站】python赋值和交换的方法
文章评论
评论问答