黄婉伶黄婉君,江苏卫视的非诚勿扰,肉松茸
回文
利用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
最长回文子序列
动态规划法
# 求得最长回文子序列的长度
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实现常见的回文字符串算法，希望对大家有所帮助
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
新手学习Python2和Python3中print不同的用法
Python基于os.environ从windows获取环境变量
网友评论