回文
利用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 1RL-1: 0 1 0 3 0 1 0i: 0 1 2 3 4 5 6char: # a # b # a # b #RL: 1 2 1 4 1 4 1 2 1RL-1: 0 1 0 3 0 3 0 1 0i: 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 => abbcabababb => ababasogou => 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 # 添加 aabcd -> 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實現常見的回文字符串算法，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復大家的。在此也非常感謝大家對VEVB武林網網站的支持！
新聞熱點
疑難解答
