LeetCode刷題實(shí)戰(zhàn)5：判斷回文子串

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

https://leetcode.com/problems/longest-palindromic-substring/

翻譯

給定一個(gè)字符串s，要求它當(dāng)中的最長回文子串。可以假設(shè)s串的長度最大是1000。

Example 1:
Input: "babad"Output: "bab"Note: "aba" is also a valid answer.Example 2:
Input: "cbbd"Output: "bb"

這道題中利用回文串的性質(zhì)還有一個(gè)trick，對(duì)于一個(gè)字符串S，如果我們對(duì)它進(jìn)行翻轉(zhuǎn)，得到S_，顯然它當(dāng)中的回文子串并不會(huì)發(fā)生變化。所以如果我們對(duì)翻轉(zhuǎn)前后的兩個(gè)字符串求最長公共子序列的話，得到的結(jié)果就是回文子串。

算法導(dǎo)論當(dāng)中對(duì)這個(gè)問題的講解是使用動(dòng)態(tài)規(guī)劃算法，即是對(duì)于字符串S中所有的位置i和S_中所有的位置j，我們用一個(gè)dp數(shù)組記錄下以i和j結(jié)尾的S和S_的子串能夠組成的公共子序列的最大的結(jié)果。

顯然，對(duì)于i=0，j=0，dp[i][j] = 0（假設(shè)字符串下標(biāo)從1開始）

我們寫出DP的代碼：

for i in range(1, n):  for j in range(1, m):    if S[i] == S_[j]:      dp[i][j] = dp[i-1][j-1] + 1    else:      dp[i][j] = max(dp[i-1][j], dp[i][j-1])

我們不難觀察出來，這種解法的復(fù)雜度同樣是。并且空間復(fù)雜度也是O(n)，也就是說我們費(fèi)了這么大勁，并沒有起到任何優(yōu)化。所以從這個(gè)角度來看，暴力搜索并不是這題當(dāng)中很糟糕的解法。

分析到了這里，也差不多了，下面我們直接進(jìn)入正題，這題的最佳解法，O(n)時(shí)間內(nèi)獲取最大回文子串的曼徹斯特算法。

def preprocess(text):    new_str = '#'    for c in text:        new_str += c + '#'    return new_str

曼切斯特算法用到三個(gè)變量，分別是數(shù)組p，idx和mr。我們接下來一個(gè)一個(gè)介紹。

首先是數(shù)組radis，它當(dāng)中存在的是每個(gè)位置能構(gòu)成的最長回文串的半徑。注意，這里不是長度，是半徑。

我們舉個(gè)例子：

字符串S     # a # b # b # a #radis      1 2 1 2 5 2 1 2 1

?

此時(shí)i小于mr，mr對(duì)應(yīng)的回文中心是id。那么i在id的回文范圍當(dāng)中，對(duì)于i而言，我們可以獲取到它關(guān)于id的對(duì)稱位置：id * 2 - i，我們令它等于i_。知道這個(gè)對(duì)稱的位置有什么用呢？很簡單，我們可以快速的確定radis[i]的下界。在遍歷到i的時(shí)候，我們已經(jīng)有了i_位置的結(jié)果。通過i_位置的結(jié)果，我們可以推算i位置的范圍。

radis[i]? >= min(radis[i_], mr-i)

為什么是這個(gè)結(jié)果呢？

我們把情況寫全，假設(shè)mr-i > radis[i_]。那么i_位置的回文串全部都落在id位置的回文串里。這個(gè)時(shí)候，我們可以確定radis[i]=radis[i_]。為什么呢？

因?yàn)楦鶕?jù)對(duì)稱原理，如果以i為中心的回文串更長的話，我們假設(shè)它的長度是radis[i_]+1。會(huì)導(dǎo)致什么后果呢？如果這個(gè)發(fā)生，那么根據(jù)關(guān)于id的對(duì)稱性，這個(gè)字符串關(guān)于id的對(duì)稱位置也是回文的。那么radis[i_1]也應(yīng)該是這么多才對(duì)，這就構(gòu)成了矛盾。如果你從文字描述看不明白的話，我們來看下面這個(gè)例子：

S:       c a b c b d b c b a cradis:     x_  i_  5   i   x

字符串S     XXXXXXXXSXXXXXXXXXXXXXXXradis        i_    id    i mr

在上圖這個(gè)例子當(dāng)中，i_的位置的回文串向左只能延伸到ml，因?yàn)閙l-1的位置和關(guān)于i_對(duì)稱的位置不相等。對(duì)于mr的右側(cè)，它完全可以既和i點(diǎn)對(duì)稱，又不會(huì)影響raids[id]的正確性。這個(gè)時(shí)候，我們就可以通過循環(huán)繼續(xù)遍歷，拓展i位置的回文串。

整個(gè)過程的分析雖然很多，也很復(fù)雜，但是寫成代碼卻并不多。

# 初始化idx, mr = 0, 0# 為了防止超界，設(shè)置字符串從1開始for i in range(1, n):  # 通過對(duì)稱性直接計(jì)算radis[i]  radis[i] = 1 if mr < i else min(radis[2 * idx - i], mr - i)  # 只有radis[i_] = mr - i的時(shí)候才繼續(xù)往下判斷  if radis[2 * idx - i] != mr - i and mr > i:    continue  # 繼續(xù)往下判斷后面的位置  while s[radis[i] + i] == s[i - radis[i]]:    radis[i] += 1  # 更新idx和mr的位置  if radis[i] + i > mr:    mr = radis[i] + i    idx = i

到這里，曼切斯特算法就算是實(shí)現(xiàn)完了。雖然我們用了這么多篇幅去介紹它，可是真正寫出來，它只有幾行代碼而已。不得不說，實(shí)在是非常巧妙，第一次學(xué)習(xí)可能需要反復(fù)思考，才能真正理解。

不過我們還有一個(gè)問題沒有解決，為什么這樣一個(gè)兩重循環(huán)的算法會(huì)是 O（n）的復(fù)雜度呢？

想要理解這一點(diǎn)，需要我們拋開所有的虛幻來直視本質(zhì)。雖然我們并不知道循環(huán)進(jìn)行了多少次，但是有兩點(diǎn)可以肯定。通過這兩點(diǎn)，我們就可以抓到復(fù)雜度的本質(zhì)。

第一點(diǎn)，mr是遞增的，只會(huì)變大，不會(huì)減小。

第二點(diǎn)，mr的范圍是0到n，每次mr增加的數(shù)量就是循環(huán)的次數(shù)。

所以即使我們不知道m(xù)r變化了多少次，每次變化了多少，我們依然可以確定，這是一個(gè)O（n）的算法。

如果喜歡本文，請(qǐng)順手點(diǎn)個(gè)贊或者轉(zhuǎn)發(fā)吧。