回文

利用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

最長的回文子串

暴力破解

暴力破解，枚舉所有的子串，對(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  # 枚舉子串的長度  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        # 保存最長的回文起點(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ù)長度, 插入的是同樣的符號(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 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: 我們發(fā)現(xiàn) RL[i] -1 正好是初始字符串中以位置i 為對(duì)稱軸的最長回文長度

所以下面就是重點(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)