Python实现常见的回文字符串算法_Python

回文

利用python 自带的翻转函数 reversed()

1	`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]

添加字符生成最短回文字符串

这道题其实跟上面基本是一样的，

实例：

1 2	`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实现常见的回文字符串算法/

Python实现常见的回文字符串算法

相关文章

热门资讯