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

2024-12-13 05:35:07

回文

利用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实现常见的回文字符串算法，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对我们网站的支持！

Python求一批字符串的最长公共前缀算法示例

本文实例讲述了Python求一批字符串的最长公共前缀算法.分享给大家供大家参考,具体如下: 思路一:这个题一拿到手,第一反应就是以第一个字符串strs[0]为标准,如果其他字符串的第一个字符和str[0]的第一个字符串相同,则再比较第二个字符串,以此类推直到出现不同为止. def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ if not st
Python实现的破解字符串找茬游戏算法示例

本文实例讲述了Python实现的破解字符串找茬游戏算法.分享给大家供大家参考,具体如下: 最近在一个QQ群里发现有那种机器人, 发出来字符串找茬游戏: 有点类似于: 没没没没没没没没没没没没没没没没没没没没没没没没没没没没没没没没没没没没没没没没没役没没没没没没没没没没没没没没没没没没没没役没没没没没没没没没没没没没没没没没没没没没没没没没没没没没没没没没没没没没没没没没没没没没玩法就是用户发消息到群里: #找茬然后群里有个自动聊天的机器人, 他接到这句话之后, 会将上面一大堆文字
Python实现查找字符串数组最长公共前缀示例

本文实例讲述了Python实现查找字符串数组最长公共前缀.分享给大家供大家参考,具体如下: 编写一个函数来查找字符串数组中的最长公共前缀. class Solution: def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ olds = '' rs='' if not strs: return '' if len(strs)==1: retu
Python字符串匹配算法KMP实例

本文实例讲述了Python字符串匹配算法KMP.分享给大家供大家参考.具体如下: #!/usr/bin/env python #encoding:utf8 def next(pattern): p_len = len(pattern) pos = [-1]*p_len j = -1 for i in range(1, p_len): while j > -1 and pattern[j+1] != pattern[i]: j = pos[j] if pattern[j+1] == pattern
Python实现字符串匹配算法代码示例

字符串匹配存在的问题 Python中在一个长字符串中查找子串是否存在可以用两种方法:一是str的find()函数,find()函数只返回子串匹配到的起始位置,若没有,则返回-1:二是re模块的findall函数,可以返回所有匹配到的子串. 但是如果用findall函数时需要注意字符串中存在的特殊字符蛮力法字符串匹配: 将模式对准文本的前m(模式长度)个字符,然后从左到右匹配每一对对应的字符,直到全部匹配或遇到一个不匹配的字符.后一种情况下,模式向右移一位. 代码如下: def string_m
python 实现求解字符串集的最长公共前缀方法

问题比较简单,给定一个字符串集合求解其中最长的公共前缀即可,这样的问题有点类似于最长公共子序列的问题,但是比求解最长最长公共子序列简单很多,因为是公共前缀,这样的话只需要挨个遍历即可,只要遍历长度结束或者结束前发现有不相同的即可终止,返回不同位置之前的子序列即可,下面是具体的实现: #!usr/bin/env python #encoding:utf-8 ''' __Author__:沂水寒城功能:求解字符串集的最长公共前缀 ''' def find_longest_prefix(str_li
python之消除前缀重命名的方法

● 脚本用途遍历文件夹下的文件,消除文件名前的特征字符串. ● 脚本实现 import os,sys import re from string import Template div = r"." ############################################################################### # @Function: description #######################################
Python查找最长不包含重复字符的子字符串算法示例

本文实例讲述了Python查找最长不包含重复字符的子字符串算法.分享给大家供大家参考,具体如下: 题目描述请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度.例如在"arabcacfr"中,最长的不包含重复字符的子字符串是"acfr",长度为4 采用字典的方法,最后输出所有最长字符的列表算法示例: # -*- coding:utf-8 -*- #! python3 class Solution: def __init__(self):
python使用正则表达式来获取文件名的前缀方法

在我们处理文件的时候,会遇到这样的一种场景,我们需要对某个文件进行操作,然后生成与原文件名相同的文件(只是文件格式改变).那么这个时候就可以使用正则表达式来匹配我们所需要的字符串. 实现 import re test='kasduabshdvkjASVKDV.txt' m=re.findall(r'(.+?)\.',test) print(m) 我们所使用的是python正则表达式库,re库来进行快速正则匹配.对此不熟悉的朋友可以去看看相关的知识.在这里我简单的说下 r'(.+?)\.'这里面的
Python实现常见的回文字符串算法

回文利用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]
Python回文字符串及回文数字判定功能示例

本文实例讲述了Python回文字符串及回文数字判定功能.分享给大家供大家参考,具体如下: 所谓回文字符串,就是一个字符串,从左到右读和从右到左读是完全一样的.回文数字也是如此. python2代码如下: def huiwen(s): s1=str(s) if s1==''.join(reversed(s1)): return True else: return False 运行结果: >>> huiwen('abccba') True >>> huiwen('abc')
Python实现判断一个整数是否为回文数算法示例

本文实例讲述了Python实现判断一个整数是否为回文数算法.分享给大家供大家参考,具体如下: 第一个思路是先将整数转换为字符串,再将字符串翻转并与原字符串做比较 def isPalindrome(self, x): """ :type x: int :rtype: bool """ #思路:先将整数转换为字符串,再将字符串翻转并与原字符串做比较 x = str(x) return x == x[::-1] 代码简洁第二个思路,尝试着不用字符串,
Python3最长回文子串算法示例

本文实例讲述了Python3最长回文子串算法.分享给大家供大家参考,具体如下: 1. 暴力法思路:对每一个子串判断是否回文 class Solution: def longestPalindrome(self, s): """ :type s: str :rtype: str """ if len(s) == 1: return s re = s[0] for i in range(0,len(s)-1): for j in range(i+1
Python3实现的判断回文链表算法示例

本文实例讲述了Python3实现的判断回文链表算法.分享给大家供大家参考,具体如下: 问题: 请判断一个链表是否为回文链表. 方案一:指针法 class Solution: def isPalindrome(self, head): """ 判断一个链表是否是回文的,很自然的想法就是两个指针,一个指针从前往后走,一个指针从后往前走,判断元素值是否相同,这里要分几个步骤来进行求解: 1.找到链表长度的一半,用追赶法,一个指针一次走两步,一个指针一次走一步 2.将后一半数组转置
C++实现LeetCode(验证回文字符串)

[LeetCode] 125.Valid Palindrome 验证回文字符串 Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. For example, "A man, a plan, a canal: Panama" is a palindrome. "race a car" is not a
C++实现LeetCode(125.验证回文字符串)

[LeetCode] 125.Valid Palindrome 验证回文字符串 Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. For example, "A man, a plan, a canal: Panama" is a palindrome. "race a car" is not a
C++/C 回文字符串的实例详解

C++/C回文字符串的实例详解判断输入的字符串是不是回文字符串,正反读一样. .C版 #include<stdio.h> int main() { char he[100]; char a; int i=0,flag=1; while((a=getchar())!='\n') { he[i]=a; i++; } int n=i; for(i=0;i<n/2;i++) { printf("%c\t%c\n",he[i],he[n-1-i]); if(he[i]!=he
PHP判断一个字符串是否是回文字符串的方法

本文实例讲述了PHP判断一个字符串是否是回文字符串的方法.分享给大家供大家参考.具体实现方法如下: <?php function ishuiwen($str){ $len=strlen($str); $l=1; $k=intval($len/2)+1; for($j=0;$j<$k;$j++){ if (substr($str,$j,1)!=substr($str,$len-$j-1,1)) { $l=0; break; } } if ($l==1) { return 1; } else {
C#递归实现回文判断算法

本文实例讲述了C#递归实现回文判断算法,分享给大家供大家参考.具体实现方法如下: 复制代码代码如下: static void Main(string[] args) { DateTime dt1 = DateTime.Now; string text = "abcdedcba"; bool bYes = Recv(text); Console.Write("{0}:{1}回文!", text, bYes ? "是" :

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

相关推荐

随机推荐