Python实现常见的回文字符串算法
作者:小歪的博客 发布时间:2022-07-10 10:32:29
回文
利用python 自带的翻转 函数 reversed()
def is_plalindrome(string): return string == ''.join(list(reversed(string)))`自己实现
def is_plalindrome(string):
string = list(string)
length = len(string)
left = 0
right = length - 1
while left < right:
if string[left] != string[right]:
return False
left += 1
right -= 1
return True最长的回文子串
暴力破解
暴力破解,枚举所有的子串,对每个子串判断是否为回文, 时间复杂度为 O(n^3)
动态规划
def solution(s):
s = list(s)
l = len(s)
dp = [[0] * l for i in range(l)]
for i in range(l):
dp[i][i] = True
# 当 k = 2时要用到
dp[i][i - 1] = True
resLeft = 0
resRight = 0
# 枚举子串的长度
for k in range(2, l+1):
# 子串的起始位置
for i in range(0, l-k+1):
j = i + k - 1
if s[i] == s[j] and dp[i + 1][j - 1]:
dp[i][j] = True
# 保存最长的回文起点和终点
if resRight - resLeft + 1 < k:
resLeft = i
resRight = j
return ''.join(s[resLeft:resRight+1])
时间复杂度为 O(n^2), 空间复杂度为 O(n^2)
Manacher 算法
Manacher 算法首先对字符串做一个预处理,使得所有的串都是奇数长度, 插入的是同样的符号且符号不存在与原串中,串的回文性不受影响
aba => #a#b#a#abab => #a#b#a#b#`
我们把回文串中最右位置与其对称轴的距离称为回文半径,Manacher 算法定义了一个回文半径数组 RL,RL[i]表示以第 i 个字符为对称轴的回文半径,对于上面得到的插入分隔符的串来说,我们可以得到 RL数组
char: # a # b # a #
RL: 1 2 1 4 1 2 1
RL-1: 0 1 0 3 0 1 0
i: 0 1 2 3 4 5 6
char: # a # b # a # b #
RL: 1 2 1 4 1 4 1 2 1
RL-1: 0 1 0 3 0 3 0 1 0
i: 0 1 2 3 4 5 6 7 8我们还求了 RL[i] - 1: 我们发现 RL[i] -1 正好是初始字符串中以位置i 为对称轴的最长回文长度
所以下面就是重点如何求得 RL 数组了, 可以参考这篇 文章 (讲得比较清晰)
下面是算法实现
def manacher(preS):
s = '#' + '#'.join(preS) + '#'
l = len(s)
RL = [0] * l
maxRight = pos = maxLen = 0
for i in range(l):
if i < maxRight:
RL[i] = min(RL[2*pos - i], maxRight-i)
else:
RL[i] = 1
while i - RL[i] >= 0 and i + RL[i] < l and s[i - RL[i]] == s[i + RL[i]]:
RL[i] += 1
if i + RL[i] - 1 > maxRight:
maxRight = i + RL[i] - 1
pos = i
maxLen = max(RL)
idx = RL.index(maxLen)
sub = s[idx - maxLen + 1: idx + maxLen]
return sub.replace('#', '')
空间复杂度:借助了一个辅助数组,空间复杂度为 O(n)
时间复杂度:尽管内层存在循环,但是内层循环只对尚未匹配的部分进行,对于每一个字符来说,只会进行一次,所以时间复杂度是 O(n)
最长回文前缀
所谓前缀,就是以第一个字符开始
下面的最长回文前缀
abbabbc => abbc
abababb => ababa
sogou => s
将原串逆转,那么问题就转变为求原串的前缀和逆串后缀 相等且长度最大的值 , 这个问题其实就是 KMP 算法 中的 next 数组的求解了
具体求解: 将原串逆转并拼接到原串中, 以'#' 分隔原串和逆转避免内部字符串干扰。
def longest_palindrome_prefix(s):
if not s:
return 0
s = s + '#' + s[::-1] + '$'
i = 0
j = -1
nt = [0] * len(s)
nt[0] = -1
while i < len(s) - 1:
if j == -1 or s[i] == s[j]:
i += 1
j += 1
nt[i] = j
else:
j = nt[j]
return nt[len(s) - 1]添加字符生成最短回文字符串
这道题其实跟上面基本是一样的,
实例:
aacecaaa -> aaacecaaa # 添加 a
abcd -> dcbabcd # 添加 dcb我们先求字符串的最长回文前缀, 然后剩余的字符串逆转并拼接到字符串的头部即是问题所求
def solution(s):
length = longest_palindrome_prefix(s)
return s[length:][::-1] + s最长回文子序列
动态规划法
dp[i][j] 表示子序列 s[i..j] 中存在的最长回文子序列长度
初始化dp[i][i] = 1
当 s[i] == s[j] 为 true 时,dp[i][j] = dp[i+1][j - 1] + 2
当 s[i] == s[j] 为 false 时,dp[i][j] = max(dp[i+1][j], dp[i][j - 1])
# 求得最长回文子序列的长度
def solution(s):
l = len(s)
dp = [[0] * l for i in range(l)]
for i in range(l):
dp[i][i] = 1
# 枚举子串的长度
for k in range(2, l+1):
# 枚举子串的起始位置
for i in range(0, l-k+1):
j = i + k - 1
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])
return dp[0][l-1]
时间复杂度为 O(n^2), 空间复杂度为 O(n^2)
总结
以上所述是小编给大家介绍的Python实现常见的回文字符串算法网站的支持!
来源:https://zhangslob.github.io/2018/11/13/Python实现常见的回文字符串算法/
猜你喜欢
- 以前我也写过一个注册表类,不过那一个不能进行多个类的注册,下面用数组对类进行了存储。 <?php //基础类 class webSit
- 阿里云 视频直播 配置 及 PHP-SDK 接入教程个人感觉,阿里的文档比微信的要坑很多…微信最多是有些比较重要的东西放到比较不起眼、比较难
- 当数据库的数据量读写频繁的时候,我们就要考虑把数据库的读写分开,以提高数据库的使用效率,(当然还有其他用处比如,备份数据),这个时候我们就要
- js汉字简繁转换源代码:<html> <head> <title>汉字简繁转换工具_asp之家</
- 互联网的真正算得上成功的产品屈指可数,每年都有成千上万个新网站出现,同时也有成千上万的网站死去,而那些算得上成功的产品,无不是从这些尸骨堆里
- 前端实现用ligerUI实现分页,感觉用框架确实简单,闲着无聊,模拟着liger的分页界面实现了一遍(只要是功能,样式什么无视)
- pandas中包含了DataFrame和Series数据类型,分别表示二维数据结构和一维数据结构。简单的可以理解为Series为excel表
- 本文为大家分享了python2.7和NLTK安装教程,具体内容如下系统:Windows 7 Ultimate 64-bitsPython 2
- 举例如下:<HTML> <HEAD>  
- 本文实例总结了Python3.5字符串常用操作。分享给大家供大家参考,具体如下:一、输入与输出#输入与输出str = input("
- 前言在设计用例的时候,有些用例只是参数数据的输入不一样,比如登录这个功能,操作过程是一样的.如果重复去写操作过程会增加代码量,对应这种多组数
- 1.创建空字典>>> dic = {}>>> type(dic)<type 'dict
- 客户的一台服务器出现Raid故障,经过我们的努力,数据基本恢复成功,但是其中的一个SQL Server日志文件(扩展名LDF)损坏严重,基本
- sql2000的服务器版本是8.0,sql2005是9.0首先要读安装必须配置(见后记)1.我是先装2000的,安装好后打上sp4补丁,(s
- 组合集总计: group by with rollup/cube grouping sets 子查询按执行方式分:标准子查询、关联子查询 标
- 随着对称密码的发展,DES数据加密标准算法由于密钥长度较小(56位),已经不适应当今分布式开放网络对数据加密安全性的要求,因此1997年NI
- 1、基本概念K近邻法(K-nearest neighbors,KNN)既可以分类,也可以回归。KNN做回归和分类的区别在于最后预测时的决策方
- 安装环境:python版本2.7.5 ,win7系统安装Djangohttps://www.djangoproject.com/downlo
- jsp登陆验证,网页登陆验证带验证码校验,登录功能之添加验证码part_1:专门用于生成一个验证码图片的类:VerificationCode
- Python中实现socket通信的服务端比较复杂,而客户端非常简单,所以客户端基本上都是用sockct模块实现,而服务 端用有很多模块可以