导语:
本文主要介绍了关于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
本文教程操作环境:windows7系统、Python 3.9.1,DELL G3电脑。
本文为原创文章,版权归知行编程网所有,欢迎分享本文,转载请保留出处!
你可能也喜欢
- ♥ Python中获取cookie有什么用11/01
- ♥ 什么是 python EasyOCR 库10/16
- ♥ Python 如何从文件中读取数据10/04
- ♥ Python导入运行模块的原理11/15
- ♥ python时间库有哪些时钟12/27
- ♥ Python实战:filter()函数中使用None进行过滤10/04
内容反馈