動(dòng)態(tài)規(guī)劃、馬拉車算法
題目描述
給你一個(gè)字符串 s，找到 s 中最長(zhǎng)的回文子串。
示例 1：
輸入： s = "babad"
輸出： "bab"
解釋： "aba" 同樣是符合題意的答案。
示例 2：
輸入： s = "cbbd"
輸出： "bb"
示例 3：
輸入： s = "a"
輸出： "a"
示例 4：
輸入： s = "ac"
輸出： "a"
提示：
1 <= s.length <= 1000-
s僅由數(shù)字和英文字母（大寫和/或小寫）組成
思路
這是一個(gè)經(jīng)典的算法問(wèn)題，解決該問(wèn)題的方法有很多。典型的解法有雙指針動(dòng)態(tài)規(guī)劃，中心求臂展解法，以及臂展解法的進(jìn)階解法馬拉車算法。
三種解法的復(fù)雜度如下表。（設(shè) n = s.length）
| 解決方法 | 時(shí)間復(fù)雜度 | 空間復(fù)雜度 |
|---|---|---|
| 普通動(dòng)態(tài)規(guī)劃 | O(n^2) | O(n^2) |
| 臂展計(jì)算法 | O(n^2) | O(1) |
| 拉馬車算法 | O(n) | O(n) |
下面分別介紹下三種算法的解題思路。
普通動(dòng)態(tài)規(guī)劃解法
由于本問(wèn)題要求的回文子串是一個(gè)子字符串，我們很自然的就會(huì)用s[i...j]定義該子串，其中j >= i。
那么，進(jìn)一步思考的問(wèn)題就是，如何判斷s[i...j]是一個(gè)子串？
可以分三步來(lái)分析。
- 當(dāng)子串長(zhǎng)度為
1，即j - i == 0時(shí)，因?yàn)橹挥幸粋€(gè)字符，該子串必然是回文子串。 - 當(dāng)子串長(zhǎng)度為
2，即j - i == 1時(shí)，顯然只要s[i] == s[j]，該子串則為回文子串，否則就不是回文子串。 - 當(dāng)子串長(zhǎng)度大于
2，即j - i > 1時(shí)，要考察子串是否為回文子串，則需要進(jìn)行如下考察。
針對(duì)情況3的考察。
- 如果
s[i] != s[j]，則該子串必然不是回文子串。 - 如果
s[i] == s[j]，則該子串是否是回文子串，取決于s[i+1...j-1]是否是回文子串。
經(jīng)過(guò)以上的分析，我們成功的把該問(wèn)題轉(zhuǎn)換成了一個(gè)動(dòng)態(tài)規(guī)劃問(wèn)題。
我們還可以對(duì)長(zhǎng)度為1和2的邊界條件做進(jìn)一步優(yōu)化，可以假定當(dāng)字符串為空時(shí)，我們認(rèn)為空字符串是特殊的回文子串。這么一來(lái)，情況2就可以被合并到情況3里。
將以上思路用代碼進(jìn)行表達(dá)?？梢酝ㄟ^(guò)這樣一個(gè)編碼思路：
- 通過(guò)循環(huán)來(lái)遍歷回文子串。
- 為了保證能通過(guò)動(dòng)態(tài)規(guī)劃緩存上一次的計(jì)算結(jié)果，我們先從長(zhǎng)度為
2的回文子串開始進(jìn)行查找（長(zhǎng)度為1沒(méi)必要查找），一直查到長(zhǎng)度為n為止。 - 當(dāng)我們查找長(zhǎng)度為
l的子串時(shí)，由于循環(huán)迭代的關(guān)系，我們已經(jīng)找過(guò)長(zhǎng)度小于l的子串計(jì)算結(jié)果了，這樣就可以通過(guò)讀取上一次的計(jì)算結(jié)果進(jìn)行本次計(jì)算。
代碼如下。
class Solution {
func longestPalindrome(_ s: String) -> String {
let cs = s.cString(using: .ascii)!
let n = strlen(cs)
// 二維數(shù)組`c`用來(lái)緩存長(zhǎng)度大于等于2的回文子串判定
// 默認(rèn)值為false
var c: [[Bool]] = Array(repeating: Array(repeating: false, count: n),
count: n)
// 確保n > 1，否則n <= 1的話直接返回字符串即可
// 因?yàn)樗隙ㄊ腔匚淖哟? guard n > 1 else { return s }
// 保存一個(gè)最長(zhǎng)回文子串的長(zhǎng)度和子串范圍索引
var maxlen = 0
var rng: (Int, Int) = (0, 0)
// 尋找從2到n長(zhǎng)度的回文子串
for l in 2...n {
// 開始遍歷索引
for i in 0..<n-l+1 {
// 只有首尾相等時(shí)才有可能是回文子串
if cs[i] == cs[i+l-1] && (l <= 3 || c[i+1][i+l-2]) {
// 保存計(jì)算結(jié)果
c[i][i+l-1] = true
if l > maxlen {
rng = (i, i+l-1)
maxlen = l
}
}
}
}
return String(cString: cs[rng.0...rng.1].map{$0} + [0])
}
}
由于該算法明顯用了兩層循環(huán)進(jìn)行計(jì)算，而且還開辟了一個(gè)二維緩存數(shù)組。顯然時(shí)間復(fù)雜度是O(n^2)，空間復(fù)雜度也是O(n^2)。
臂展計(jì)算法
因?yàn)榛匚拇幸粋€(gè)特性，從串的中間往左右觀察的話，可以發(fā)現(xiàn)左右兩邊是相等的，從這個(gè)思路出發(fā)就可以考慮到，任何回文串都存在一個(gè)中間界，當(dāng)從中間界往左右擴(kuò)散，必然可以得出左右兩邊的字符是相等的。
假定有一個(gè)回文串s[i..k..j]，且其長(zhǎng)度為奇數(shù)，其中i<=k<=j，且k=(i+j)/2，那么k就是該回文串的中位數(shù)，當(dāng)回文串足夠長(zhǎng)時(shí)，我們有s[k+1]=s[k-1]，s[k+2]=s[k-2]，s[k+3]=sk[k-3]……直到碰到i和j為止。
以上分析僅限于回文串長(zhǎng)度為奇數(shù)時(shí)，那么當(dāng)長(zhǎng)度為偶數(shù)時(shí)呢，我們可以這樣定義，對(duì)于一個(gè)回文串s[i..k..j]，且其長(zhǎng)度為偶數(shù)，其中i<=k<=j，且k=(i+j-1)/2，那么k就是該回文串的中位數(shù)，當(dāng)回文串足夠長(zhǎng)時(shí)，我們有s[k]=s[k+1]，s[k-1]=s[k+2]，s[k-2]=s[k+3]……直到碰到i和j為止。
通過(guò)對(duì)中位數(shù)k的分析，可以把循環(huán)的思路從“找i”引到“找k”，即我們掃描數(shù)組中的所有元素，并且我們尋找它是回文串的中位數(shù)時(shí)最長(zhǎng)的回文串有多長(zhǎng)，該長(zhǎng)度我們稱之為它的“臂展“。
由于前面分析的中位數(shù)k存在兩種情況，即臂展為偶數(shù)和臂展為奇數(shù)的情況，所以我們需要設(shè)計(jì)一個(gè)函數(shù)來(lái)計(jì)算偶數(shù)和奇數(shù)情況下的臂展。
func searchSpan(_ k: Int, _ x: Bool) -> Int {
var i = 1
let t = x ? 0 : 1
while k - i + t >= 0 && k + i < n && cs[k-i+t] == cs[k+i] {
i += 1
}
return x ? i * 2 - 1 : (i - 1) * 2
}
在該函數(shù)searchSpan中，其參數(shù)k為中位數(shù)，參數(shù)x為布爾類型，知名所求回文串長(zhǎng)度為奇數(shù)還是偶數(shù)。cs代表著字符串。
當(dāng)循環(huán)i從1開始計(jì)數(shù)時(shí)，對(duì)于奇數(shù)臂展，求的是cs[i-1]和cs[i+1]的比較，而對(duì)于偶數(shù)臂展，求的是cs[i]和cs[i+1]的比較。
對(duì)于奇數(shù)和偶數(shù)，通過(guò)一個(gè)變量t來(lái)進(jìn)行邊界增量計(jì)算。
最后輸出臂展的長(zhǎng)度，同樣是分奇數(shù)和偶數(shù)來(lái)計(jì)算。
有了求臂展函數(shù)，接下來(lái)的操作就相對(duì)簡(jiǎn)單了，我們只要遍歷整個(gè)字符串，求得臂展，然后保存最大臂展和臂展的范圍，當(dāng)循環(huán)結(jié)束時(shí)，最大的臂展范圍已經(jīng)求得。
完整代碼如下。
class Solution {
func longestPalindrome(_ s: String) -> String {
let cs = s.cString(using: .ascii)!
let n = strlen(cs)
func searchSpan(_ k: Int, _ x: Bool) -> Int {
var i = 1
let t = x ? 0 : 1
while k - i + t >= 0 && k + i < n && cs[k-i+t] == cs[k+i] {
i += 1
}
return x ? i * 2 - 1 : (i - 1) * 2
}
var maxLen = 0
var rng = (0, 0)
for k in 0..<n {
let l1 = searchSpan(k, true)
let l2 = searchSpan(k, false)
let l = max(l1, l2)
if l > maxLen {
rng = l1 > l2 ? (k-l1/2, k+l1/2) : (k-l2/2+1, k+l2/2)
maxLen = l
}
}
return String(cString: cs[rng.0...rng.1].map{$0}+[0])
}
}
該算法總共有兩層循環(huán)，不難分析出其時(shí)間復(fù)雜度為O(n^2)，由于該算法額外開辟的空間是常量級(jí)別，故其空間復(fù)雜度為O(1)。
馬拉車算法
馬拉車算法的英文名叫Manacher‘s Algorithm，是一個(gè)卡內(nèi)基梅隆大學(xué)的計(jì)算機(jī)教授Glenn Keith Manacher發(fā)明的算法，該算法可以實(shí)現(xiàn)在O(n)時(shí)間復(fù)雜度內(nèi)解決最大回文子串的查找問(wèn)題。
馬拉車算法事實(shí)上是臂展算法的改進(jìn)版。它的起點(diǎn)思路和臂展算法是一致的，即計(jì)算每個(gè)遍歷節(jié)點(diǎn)的臂展，但是它會(huì)保存臂展的結(jié)果以便于下次可以”跳過(guò)”不必要的計(jì)算。
我們假設(shè)對(duì)于字符串s，遍歷i求其臂展，并且位置i的臂展長(zhǎng)度是奇數(shù)，那么s[i]必然位于該回文子串的正中央位置，將臂展長(zhǎng)度分為左右兩側(cè)的等臂，取右臂的長(zhǎng)度為l，那么，當(dāng)我們將i向后遍歷到j時(shí)，如果j還在臂展范圍內(nèi)，我們會(huì)發(fā)現(xiàn)當(dāng)l足夠長(zhǎng)時(shí)，因?yàn)?code>i左右兩側(cè)的數(shù)值是鏡像關(guān)系，對(duì)于s[j]，必然存在臂展左邊的鏡像s[i-(j-i)]，而因?yàn)樽髠?cè)的對(duì)應(yīng)位置我們已經(jīng)計(jì)算過(guò)其臂展，那么對(duì)于位置j，我們就可以“跳過(guò)”鏡像已經(jīng)計(jì)算過(guò)的部分。
舉例字符串："pkabacabacu"
對(duì)于該字符串，我們可以算出位置5，即字符c的位置，其臂展為7，即回文串“abacaba”，我們假設(shè)已知位置5，即c字符的臂展為7，那么再往后查找時(shí)，當(dāng)我們查找到右側(cè)的位置a時(shí)，由于左邊“鏡像”的存在，我們提前知道了左側(cè)a的臂長(zhǎng)為1，那么在計(jì)算右側(cè)的a的時(shí)候，我們自然知道它的臂長(zhǎng)“至少為1”，這樣我們只要跳過(guò)1的位置去比較即可。同理，對(duì)于b，由于左側(cè)鏡像臂展是3，即右側(cè)單臂長(zhǎng)度為1，我們?cè)谇蟊壅箷r(shí)就可以跳過(guò)這個(gè)臂展去計(jì)算新的位置，而不用從頭進(jìn)行計(jì)算。但是要注意，可以跳過(guò)的位置必須是在“臂展籠罩范圍內(nèi)”。
有了以上的“跳過(guò)”思路，我們從新審視求臂展算法，就可以知道，當(dāng)我們對(duì)字符串進(jìn)行遍歷去求臂展時(shí)，我們每次都可以得到臂展最長(zhǎng)的“染指”部分，比如假設(shè)i的位置為5，而它的臂展為7，那么它的右側(cè)單臂長(zhǎng)度就是3，它的“手臂”可以延伸到位置8，那么這就意味著，位置6、7，8都被“籠罩在”5的臂展范圍，這樣我們?cè)谟?jì)算它們時(shí)始終有對(duì)應(yīng)的鏡像進(jìn)行“跳過(guò)”參照。根據(jù)貪心思路，我們?cè)诒闅v數(shù)組時(shí)始終都會(huì)保留那個(gè)最大的籠罩范圍進(jìn)行計(jì)算。
問(wèn)題分析到這里，我們還遇到一個(gè)問(wèn)題，就是我們之前討論的是臂展長(zhǎng)度為奇數(shù)的情況，那么對(duì)于臂展為偶數(shù)的情況怎么計(jì)算？
這里提供了一個(gè)解決問(wèn)題的思路：“填充法”。舉字符串“baab”為例，它是一個(gè)回文串，且臂展為偶數(shù)。接下去看用填充法怎么做到用奇數(shù)的思路去找到它，首先對(duì)字符串的每個(gè)間隔添加字符#，字符串就變成“b#a#a#b”，那么，新的字符串對(duì)于位置3的字符#，我們找到了以它為中心的奇數(shù)回文串，而只要我們把得到的回文串清除占位符#，即可得到原回文串“baab”。
基于該算法思路編寫的完整swift代碼如下：
class Solution {
func longestPalindrome(_ s: String) -> String {
let cr = s.cString(using: .ascii)!
var n = strlen(cr)
// 由于已知字符串是ascii字符，那么可以用ascii值0作為占位符，不需要用到算法講解中的`#`
var cs: [CChar] = Array(repeating: 0, count: n*2)
var i = 0
while cr[i] != 0 {
cs[i*2] = cr[i]
i += 1
}
n = n * 2 - 1
var c: [Int] = Array(repeating: 0, count: n)
// 搜索單臂長(zhǎng)，例如臂長(zhǎng)為3，則單臂長(zhǎng)為1，如果臂長(zhǎng)為1，則單臂長(zhǎng)為0
// 參數(shù)o給定可以跳過(guò)的位移
func searchPalindrome(_ p: Int, _ o: Int) -> Int {
var i = o
while p - i >= 0 && p + i < n && cs[p - i] == cs[p + i] {
i += 1
}
return i - 1
}
var j = 0
var l = 0 // 計(jì)算到目前為止被計(jì)算的臂展覆蓋的最高索引位
var maxlen = 0
var rng: (Int, Int) = (0, 0)
for i in 0..<n {
var o = 1
if i < l {
o = min(c[j-(i-j)], l-i) // 計(jì)算可以跳過(guò)的臂展計(jì)算位移
}
let k = searchPalindrome(i, o)
// 計(jì)算臂展長(zhǎng)度（計(jì)算的是去掉占位符后的實(shí)際長(zhǎng)度）
var len = k / 2 * 2 + 1
if cs[i] == 0 {
len = (k+1) / 2 * 2
}
if len > maxlen {
maxlen = len
rng = (i-k, i+k)
}
if i + k > l {
l = i + k
j = i
}
c[i] = k
}
var ans: [CChar] = []
for i in rng.0...rng.1 {
if cs[i] != 0 {
ans.append(cs[i])
}
}
ans.append(0)
return String(cString: ans)
}
}
該算法由于每次都利用了原先的計(jì)算結(jié)果進(jìn)行跳步，其時(shí)間復(fù)雜度為O(n)，而因?yàn)樾枰?code>n同等規(guī)模的存儲(chǔ)空間，空間復(fù)雜度也為O(n)。
如果對(duì)馬拉車算法感興趣想進(jìn)一步延伸閱讀，可以看看一些介紹比較全面的國(guó)外文章，比如：https://vnspoj.github.io/wiki/string/manacher 。
小結(jié)
該題解法可難可易，一般如果是作為競(jìng)賽或者面試，方法一和二足矣，馬拉車算法更適合平時(shí)學(xué)習(xí)和嘗試，其實(shí)現(xiàn)過(guò)程并不簡(jiǎn)單，涉及到不少邊界計(jì)算，也考驗(yàn)編碼嚴(yán)謹(jǐn)程度。
所有代碼均可以在 github 下載 : https://github.com/FengHaiTongLuo/LeetCode4Swift/blob/main/5.%20Longest%20Palindromic%20Substring.swift
