首页 / 知识
python找回文子串的方法
2023-11-12 12:56:00
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学习教程请关注我们
最新内容
相关内容
python如何比较两个字符串是否相等
python如何比较两个字符串是否相等，培训，工作，字符串，两个，下面，以上，方法，更多，内容，python在实际的开发工作中，经常会遇到要判定两个字符串
python怎么调用类方法
python怎么调用类方法，培训，方法，实例，静态，定义，参数，属性，对象，关键字，以上，python中的类用来描述具有相同的属性和方法的对象的集合。它定
python如何打印列表长度
python如何打印列表长度，培训，技术，概念，项目，列表，长度，数组，方法，鲜为人知，初始化，首先，我们需要明确的一点就是Python是没有数组这一概念的
python判断元素是否是字符串类型
python判断元素是否是字符串类型，培训，异常，类型，实例，字符串，数据类型，对象，元素，参数，序列，isinstance()是Python中的一个内建函数语法：isin
python判断字符串是否包含中文
python判断字符串是否包含中文，培训，检测，代码，字符串，中文，字符，范围，空格，原理，以上，原理：中文字符的编码范围是：\u4e00-\u9fff只要编码在
python判断字符串是否为小数的方法
python判断字符串是否为小数的方法，培训，代码，合法，小数点，小数，整数，字符串，方法，右边，左边，python想判断一个字符串是不是一个合法的小数，但
python可以继承父类方法吗
python可以继承父类方法吗，培训，代码，名字，方法，动物，属性，编译器，这样的话，定义，里面，python继承,调用父类属性方法在python里面,继承一个类
python判断字符是否为字母和数字
python判断字符是否为字母和数字，数字，培训，字母，字符串，字符，空格，方法，都会，分号，大小写，在使用python语言中的字符串方法时，可以使用它们判
python函数的高级使用方法
python函数的高级使用方法，代码，函数，灵活，数据，培训，时间，定义，程序，赋值，变量，Python的函数是“一等公民”，因此函数本身也是一个对象，函数既
python字符串是对象吗
python字符串是对象吗，培训，名称，设计，对象，函数，变量，实体，参数，物件，字符串，python中一切都是对象在python中下列语句其实都是一个共同点：i=
python怎么判断是否为空字符串
python怎么判断是否为空字符串，密码，培训，字符串，空格，字符，用户名，方法，两边，长度，全部，判断python中的一个字符串是否为空，可以使用如下方法
python字符串连接的方法有哪些
python字符串连接的方法有哪些，培训，字符串，基础，方式，两个，变量，函数，空白，语言，功能，python中有很多字符串连接方式，下面总结一下：最原始的字