如何使用Python實(shí)現(xiàn)常見的回文字符串算法-創(chuàng)新互聯(lián)

小編給大家分享一下如何使用Python實(shí)現(xiàn)常見的回文字符串算法，希望大家閱讀完這篇文章之后都有所收獲，下面讓我們一起去探討吧！

創(chuàng)新互聯(lián)-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價(jià)比隆林網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫(kù),直接使用。一站式隆林網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋隆林地區(qū)。費(fèi)用合理售后完善，十余年實(shí)體公司更值得信賴。

回文

利用python 自帶的翻轉(zhuǎn) 函數(shù) reversed()

def is_plalindrome(string):  return string == ''.join(list(reversed(string)))`

自己實(shí)現(xiàn)

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

最長(zhǎng)的回文子串

暴力破解

暴力破解，枚舉所有的子串，對(duì)每個(gè)子串判斷是否為回文， 時(shí)間復(fù)雜度為 O(n^3)

動(dòng)態(tài)規(guī)劃

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
    # 當(dāng) k = 2時(shí)要用到
    dp[i][i - 1] = True
  resLeft = 0
  resRight = 0
  # 枚舉子串的長(zhǎng)度
  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
        # 保存最長(zhǎng)的回文起點(diǎn)和終點(diǎn)
        if resRight - resLeft + 1 < k:
          resLeft = i
          resRight = j
  return ''.join(s[resLeft:resRight+1])

時(shí)間復(fù)雜度為 O(n^2), 空間復(fù)雜度為 O(n^2)

Manacher 算法

Manacher 算法首先對(duì)字符串做一個(gè)預(yù)處理,使得所有的串都是奇數(shù)長(zhǎng)度, 插入的是同樣的符號(hào)且符號(hào)不存在與原串中，串的回文性不受影響

aba => #a#b#a#abab => #a#b#a#b#`

我們把回文串中最右位置與其對(duì)稱軸的距離稱為回文半徑，Manacher 算法定義了一個(gè)回文半徑數(shù)組 RL，RL[i]表示以第 i 個(gè)字符為對(duì)稱軸的回文半徑，對(duì)于上面得到的插入分隔符的串來說，我們可以得到 RL數(shù)組

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: 我們發(fā)現(xiàn) RL[i] -1 正好是初始字符串中以位置i 為對(duì)稱軸的最長(zhǎng)回文長(zhǎng)度

所以下面就是重點(diǎn)如何求得 RL 數(shù)組了， 可以參考這篇 文章 (講得比較清晰)

下面是算法實(shí)現(xiàn)

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('#', '')

空間復(fù)雜度：借助了一個(gè)輔助數(shù)組，空間復(fù)雜度為 O(n)

時(shí)間復(fù)雜度：盡管內(nèi)層存在循環(huán)，但是內(nèi)層循環(huán)只對(duì)尚未匹配的部分進(jìn)行，對(duì)于每一個(gè)字符來說，只會(huì)進(jìn)行一次，所以時(shí)間復(fù)雜度是 O(n)

最長(zhǎng)回文前綴

所謂前綴，就是以第一個(gè)字符開始

下面的最長(zhǎng)回文前綴

abbabbc => abbc
abababb => ababa
sogou => s

將原串逆轉(zhuǎn)，那么問題就轉(zhuǎn)變?yōu)榍笤那熬Y和逆串后綴 相等且長(zhǎng)度大的值 , 這個(gè)問題其實(shí)就是 KMP 算法 中的 next 數(shù)組的求解了

具體求解： 將原串逆轉(zhuǎn)并拼接到原串中， 以'#' 分隔原串和逆轉(zhuǎn)避免內(nèi)部字符串干擾。

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]

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

這道題其實(shí)跟上面基本是一樣的，

實(shí)例：

aacecaaa -> aaacecaaa # 添加 a
abcd -> dcbabcd # 添加 dcb

我們先求字符串的最長(zhǎng)回文前綴, 然后剩余的字符串逆轉(zhuǎn)并拼接到字符串的頭部即是問題所求

def solution(s):
  length = longest_palindrome_prefix(s)
  return s[length:][::-1] + s

最長(zhǎng)回文子序列

動(dòng)態(tài)規(guī)劃法

  • dp[i][j] 表示子序列 s[i..j] 中存在的最長(zhǎng)回文子序列長(zhǎng)度

  • 初始化dp[i][i] = 1

  • 當(dāng) s[i] == s[j] 為 true 時(shí)，dp[i][j] = dp[i+1][j - 1] + 2

  • 當(dāng) s[i] == s[j] 為 false 時(shí)，dp[i][j] = max(dp[i+1][j], dp[i][j - 1])

# 求得最長(zhǎng)回文子序列的長(zhǎng)度
def solution(s):
  l = len(s)
  dp = [[0] * l for i in range(l)]
  for i in range(l):
    dp[i][i] = 1
  # 枚舉子串的長(zhǎng)度
  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]

時(shí)間復(fù)雜度為 O(n^2), 空間復(fù)雜度為 O(n^2)

看完了這篇文章，相信你對(duì)“如何使用Python實(shí)現(xiàn)常見的回文字符串算法”有了一定的了解，如果想了解更多相關(guān)知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝各位的閱讀！

當(dāng)前文章：如何使用Python實(shí)現(xiàn)常見的回文字符串算法-創(chuàng)新互聯(lián)
分享URL：http://muchs.cn/article6/psdog.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供定制開發(fā)、定制網(wǎng)站、響應(yīng)式網(wǎng)站、服務(wù)器托管、全網(wǎng)營(yíng)銷推廣、做網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)

成都網(wǎng)站建設(shè)