LeetCode攀登之旅(5)

2019 年 10 月 6 日
筆記

LeetCode攀登之旅(5)

0.說在前面

1.暴力解法

2.中心枚舉法

3.動態規劃法

4.馬拉車法

5.參考文章

6.作者的話

0.說在前面

本節從求長迴文子串問題，給出四種解題方法，並深入分析馬拉車與動態規劃演算法。

【Question】

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"  Output: "bab"  Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"  Output: "bb"

1.暴力解法

【思想】

定義一個字典，並賦給初值為空，表示如果原先所給字元為空字元，直接返回，防止出現indexerror。

演算法中有三層循環，對沒錯，三層，所以你去跑leetcode，通不過，直接超出時間限制！

但是這是一種思想，得掌握，接下來說說三層循環幹了什麼事情。

外一層循環，for循環直接遍歷目標字元的長度！

中二層循環，for循環從上層的index訪問到結尾！

內三層循環，while循環，這裡是演算法核心，分別用兩個變數存儲前後的變數，然後向內靠攏，判斷是否相同，若相同，則繼續比對，不相等，則直接退出本次while循環。

每次在中二層循環嗎，添加了個count,當前面定義的收尾元素分別顛倒大小時候，即為一個迴文子串，然後重新計算count，並將其與maxcount比對。然後講初始與末尾的數進行切片即為真實的迴文子串。

【code】

class Solution:      def longestPalindrome(self, s):          s_len = len(s)          maxcount=0          s_new = {'0': ''}          for j in range(s_len):              for k in range(j,s_len):                  count = 0                  l, m=j, k                  while m >= l:                      if s[l] == s[m]:                          l, m = l+1, m-1                      else:                          break                  if m < l:                      count = k - j + 1                  if maxcount < count:                      maxcount = count                      s_new['0']=s[j:k+1]          return s_new['0']    s = Solution()  a = s.longestPalindrome('babd')  print(a)

2.中心枚舉法

【思想】

這個方法是基於上述方法的改進，每次從中心向兩邊進行擴展比對。這個演算法的注意點為，奇數與偶數問題，也就是說需要考慮目標字元串為奇數，還是偶數的問題。

【code】

class Solution:      def longestPalindrome(self, s):          """          :type s: str          :rtype: str          """          l = len(s)          if l<=1:              return s          # 定義最長迴文串          long_palindrome = ''          for i in range(l-1):              # 奇偶問題合併處理:p1與p2              p1 = self.center_expand(s,i,i)              if len(p1)>len(long_palindrome):                  long_palindrome=p1、              p2 = self.center_expand(s,i,i+1)              if len(p2)>len(long_palindrome):                  long_palindrome=p2          return long_palindrome      def center_expand(self,s,left,right):          s_len = len(s)          while left>=0 and right<s_len and s[left]==s[right]:              left-=1              right+=1          # 上述循環後,left與right是不相等的字元，所以截取字元串,是letf+1,right          return s[left+1:right]  s = Solution()  a = s.longestPalindrome('abab')  print(a)

3.動態規劃法

【思想】

上一節的0-1背包問題實現就是動態規劃法的典型例子。這個演算法的核心這裡用之前看到的一句英文解釋:

Those who cannot remember the past are condemned to repeat it.

這句話的意思是，動態規劃的思想是記住已經求過的解。對於動態規劃的具體解釋，會在今後仔細研究的演算法導論中給大家解釋。

這裡再以當前求最大迴文子串來了解一下動態規劃法的思想。

'''  分為三種情況：  第一種:檢測目標子串長度為1;  第三種:檢測目標子串長度為2;  第四種:檢測目標子串長度大於等於3;  '''

首先生成一個二維數組，然後根據遍歷的情況是否為迴文子串，標記True or False。

根據上述三種情況，下面仔細說明，並以一個實際例子進行手寫推導。

第一種：當所檢測的子串長度為1時，毋庸置疑，必然是迴文串，直接標記為True；

第二種：當所檢測的子串長度為2時，只需要判斷當前與下一個元素是否想的女即可確定該子串是否是迴文串；

第三種：當所檢測的子串長度超過2時，直接從子串長度為3進行，因為前面兩種情況已經把子串長度為1或2運算過了，那麼這個就是dp演算法的核心，對於之前已經運算過的不需要重新去運算，進而減少了時間複雜度的運算。

在第三種情況中，直接以3為跨步，便可以訪問到每個子串的末尾的字元，那麼噹噹前位置的字元與末尾字元相等，並且通過訪問之前已經存儲過的True or Fals進行比對，也就是s[i] == s[j] and dp[i + 1][j - 1]這行，這行請仔細琢磨，為dp演算法的核心之處！非常重要！

【code】

class Solution:      def longestPalindrome(self, s):          """          :type s: str          :rtype: str          """          # 獲取字元串的長度          s_len = len(s)          # 生成dp演算法的二維數組          dp = [[0] * s_len for i in range(s_len)]          if s_len == 0:              return s          # 最大長度          maxLen = 1            # 第一種：檢查目標子串長度為1          i = 0          while i < s_len:              dp[i][i] = True              i += 1            # 第二種：檢查目標子串長度為2          start = 0          i = 0          while i < s_len - 1:              if s[i] == s[i + 1]:                  dp[i][i + 1] = True                  start = i                  maxLen = 2              i += 1            # 第三種：檢查目標子串長度為大於等於3          # 遍歷長度          pal_num = 3          while pal_num <= s_len:              i = 0              # 表示循環子串長度為pal_num時,有n-pal_num+1種組合              while i < (s_len - pal_num + 1):                  # 定義子串末尾                  j = i + pal_num - 1                  # 只有再中間的數為True且兩邊一樣的情況下，才可以將其作為迴文子串                  if s[i] == s[j] and dp[i + 1][j - 1]:                      dp[i][j] = True                      if pal_num > maxLen:                          start = i                          maxLen = pal_num                  i += 1              pal_num += 1          return s[start:start + maxLen]

【手推】

子串長度為1圖

子串長度為2圖

子串長度總圖

4.馬拉車法

【思想】

對於第二種中心枚舉法我們知道，必須對奇數或偶數進行討論，那麼這就造成了不同的迴文串中心位置。

而且對於第二種方法，存在子串被重複多次訪問，造成時間的浪費，那麼我們想一下，能不能採用一種演算法直接達到線性演算法的時間，並且可以解決上述兩個問題呢。

這裡就引出了Manacher簡稱馬拉車演算法，這個演算法非常晦澀難懂，仔細閱讀後，而且在ACM大賽上不怎麼常用，一般想到上述的dp演算法，就可以了，但是我們現在是精益求精，多學幾個思想，沒什麼壞出。而且這個馬拉車演算法確實能學到很多不同的思想，如下面思想介紹。

首先解決第一個問題：原字元串奇數與偶數問題。

這個問題在馬拉車中，是通過添加特殊字元解決的，比如給定字元串abba，這個字元串為偶數，那麼插入特殊字元後，就會變為#a#b#b#a#,長度變為9，變為奇數，這個思想將所有的偶數與奇數字元串統一處理為奇數字元串！

另一個問題也就是通俗的效率問題，解決重複多次訪問的問題。這個直接從馬拉車演算法思想中去體會。

假設原字元串為S=dabbac，那麼經過插入特殊字元變為#d#a#b#b#a#c#,並即為S1[i]。

在馬拉車演算法中，通常使用一個新數組P[i]用於記錄以字元S1[i]為中心的最長迴文子串向左或向右擴張的長度，也就是迴文串長度的一半，例如：

S1     # d # a # b # b # a  #  c  #  P      1 2 1 2 1 2 5 2 1 2  1  2  1  i      0 1 2 3 4 5 6 7 8 9 10 11 12  P[i]-1 0 1 0 1 0 1 4 1 0 1  0  1  0

可以看出上述P[i]-1正好是原字元串中迴文串的總長度

【證明過程】

首先在轉換得到的字元串S1中，所有的迴文字串的長度都為奇數，那麼對於以S1[i]為中心的最長迴文字串，其長度就為2*P[i]-1,經過觀察可知，S1中所有的迴文子串，其中分隔符的數量一定比其他字元的數量多1，也就是有S1[i]個分隔符，剩下S1[i]-1個字元來自原字元串，所以該迴文串在原字元串中的長度就為P[i]-1

這裡解釋一下上述P[i]怎麼算出來的以及上面那句話的解釋！

P[0]=1 因為#號左右兩邊不相等，直接為1，P[1]=2 因為#d#，d的前後各有一個#剛好構成一個迴文子串，然後取子串的中心位置向左或向右擴張的長度，擴張各位1，再加上本身，即為2。後面的按照此方法推導即可！

以上述的字元d為例，p[1]-1=2-1=1，原字元串dabbac，可以看到d為第一個字元，以d為中心的迴文子串長度為1。

【P數組計算】

該演算法增加兩個輔助變數id和mx，其中 id 為已知的 {右邊界最大} 的迴文子串的中心，mx則為id+P[id]，也就是這個子串的右邊界。

這個演算法的關鍵點就在這裡了：如果mx > i，那麼P[i] >= MIN(P[2 * id - i], mx - i)。實際上如果把它寫得複雜一點，理解起來會簡單很多：

//記j = 2 * id - i，也就是說 j 是 i 關於 id 的對稱點(j = id - (i - id))  if (mx - i > P[j])      P[i] = P[j];  else /* P[j] >= mx - i */      P[i] = mx - i; // P[i] >= mx - i，取最小值，之後再匹配更新。

第一種情況：mx>i

當 mx - i > P[j] 的時候，以S1[j]為中心的迴文子串包含在以S[id]為中心的迴文子串中，由於 i 和 j 對稱，以S1[i]為中心的迴文子串必然包含在以S1[id]為中心的迴文子串中，所以必有 P[i] = P[j]

mx - i > P[j] 圖

當 mx - i <=P[j] 的時候以j為對稱軸的迴文串很長,只有下圖中綠色標註的地方一致

mx>mx - i <=P[j] 圖

不論上述哪種情況，之後都要更新mx與id,因為有可能得到更大的mx!

第二種情況：mx<=i

說明以i為對稱軸的迴文串還沒有任何一個部分被訪問過，於是只能從i的左右兩邊開始嘗試擴展了，當左右兩邊字元不同，或者到達字元串邊界時停止，只能P[i] = 1，然後再去匹配了。

【code】

class Solution:      def longestPalindrome(self, s):          """          :type s: str          :rtype: str          """          #預處理          t='#'+'#'.join(s)+'#'            RL=[0]*len(t)          MaxRight=0          pos=0          # MaxLen=0          for i in range(len(t)):              if i<MaxRight:                  # 或者RL[i]=min(RL[2*pos-i], MaxRight-i)                  # 上述注釋掉的這行程式碼直接等價於下面5行程式碼                  j=2*pos-i                  if MaxRight-i>RL[j]:                      RL[i]=RL[j]                  else:                      RL[i]=MaxRight-i              else:                  RL[i]=1              #嘗試擴展，注意處理邊界              while i-RL[i]>=0 and i+RL[i]<len(t) and t[i-RL[i]]==t[i+RL[i]]:                  RL[i]+=1              #更新MaxRight,pos              if RL[i] >= RL[pos]:                  MaxRight = RL[i] + i - 1                  pos = i              '''                  if RL[i]+i-1>MaxRight:                      MaxRight=RL[i]+i-1                      pos=i                  #更新最長迴文串的長度                  MaxLen=max(MaxLen, RL[i])              return MaxLen-1              '''          a=int((2*pos-MaxRight)/2)          b=int(MaxRight/2)          return s[a:b]  s = Solution()  a = s.longestPalindrome('abab')  print(a)

5.參考文章

Manacher's ALGORITHM: O(n)時間求字元串的最長迴文子串
馬拉車（Manacher）演算法最通俗教學
最長迴文子串-Manacher演算法

6.作者的話

最後，您如果覺得本公眾號對您有幫助，歡迎您多多支援，轉發，謝謝！更多刷題，請關注本公眾號演算法系列！

Tags: