LeetCode 5. Longest Palindromic SubstringLeetCode-Go 項(xiàng)目中四種 Go 解法深度剖析【免費(fèi)下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項(xiàng)目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go導(dǎo)讀本篇以 LeetCode-Go 倉(cāng)庫(kù)中 leetcode/0005.Longest-Palindromic-Substring 的官方題解文檔為主體完整拆解「最長(zhǎng)回文子串」這一經(jīng)典面試題從題目約束出發(fā)依次講解動(dòng)態(tài)規(guī)劃、中心擴(kuò)散、滑動(dòng)窗口、馬拉車Manacher四種解法在 Go 中的實(shí)現(xiàn)細(xì)節(jié)、狀態(tài)設(shè)計(jì)與復(fù)雜度分析并結(jié)合倉(cāng)庫(kù)內(nèi)的源碼與測(cè)試用例驗(yàn)證每種解法的正確性。讀完本文你將掌握最長(zhǎng)回文子串問(wèn)題的完整解法脈絡(luò)理解 Manacher 算法dp[i] min(maxRight-i, dp[2*center-i])這一核心遞推背后的原理并能直接運(yùn)行本倉(cāng)庫(kù)的測(cè)試代碼驗(yàn)證結(jié)果。題目回顧約束與輸入輸出原文檔給出了完整題目描述給定一個(gè)字符串s返回s中最長(zhǎng)的回文子串。四個(gè)官方示例s babad→bababa同樣是合法答案s cbbd→bbs a→as ac→a約束條件1 s.length 1000s僅由數(shù)字和英文字母大小寫(xiě)均可組成題目大意非常直接找到給定字符串中最長(zhǎng)的回文子串。需要注意輸出結(jié)果不唯一如示例 1只要返回其中一個(gè)合法最長(zhǎng)回文子串即可。四種解法總覽復(fù)雜度對(duì)比原文檔指出此題解法眾多本倉(cāng)庫(kù)代碼實(shí)現(xiàn)了其中四種。先看整體復(fù)雜度對(duì)比解法對(duì)應(yīng)函數(shù)時(shí)間復(fù)雜度空間復(fù)雜度核心思想解法一 Manacher馬拉車longestPalindromeO(n)O(n)預(yù)處理 對(duì)稱性復(fù)用解法二 滑動(dòng)窗口longestPalindrome1O(n2)O(1)相同字符合并 中心擴(kuò)散變體解法三 中心擴(kuò)散longestPalindrome2O(n2)O(1)枚舉奇偶兩種軸心解法四 動(dòng)態(tài)規(guī)劃longestPalindrome3O(n2)O(n2)區(qū)間 DP 狀態(tài)轉(zhuǎn)移四種實(shí)現(xiàn)全部位于源碼文件 5. Longest Palindromic Substring.go 中且全部通過(guò) 5. Longest Palindromic Substring_test.go 中的Test_Problem5測(cè)試用例驗(yàn)證。解法四動(dòng)態(tài)規(guī)劃O(n2) / O(n2)狀態(tài)定義與轉(zhuǎn)移方程定義dp[i][j]表示從字符串第i個(gè)字符到第j個(gè)字符這一段子串是否為回文串。由回文串的性質(zhì)可知回文串去掉一頭一尾相同字符后剩下的仍然是回文串。因此狀態(tài)轉(zhuǎn)移方程為dp[i][j] (s[i] s[j]) ((j-i 3) || dp[i1][j-1])其中需要特別處理兩個(gè)邊界情況j - i 1子串只有 2 個(gè)字符只需判斷這 2 個(gè)字符是否相同j - i 2子串只有 3 個(gè)字符只需判斷除去中心以外對(duì)稱的 2 個(gè)字符是否相等。這兩種情況由j-i 3統(tǒng)一覆蓋——長(zhǎng)度小于 3 的區(qū)間不需要依賴內(nèi)部子區(qū)間。Go 實(shí)現(xiàn)解析倉(cāng)庫(kù)中l(wèi)ongestPalindrome3的實(shí)現(xiàn)如下// 解法四 DP時(shí)間復(fù)雜度 O(n^2)空間復(fù)雜度 O(n^2) func longestPalindrome3(s string) string { res, dp : , make([][]bool, len(s)) for i : 0; i len(s); i { dp[i] make([]bool, len(s)) } for i : len(s) - 1; i 0; i-- { for j : i; j len(s); j { dp[i][j] (s[i] s[j]) ((j-i 3) || dp[i1][j-1]) if dp[i][j] (res || j-i1 len(res)) { res s[i : j1] } } } return res }實(shí)現(xiàn)要點(diǎn)遍歷方向外層i從len(s)-1遞減到 0因?yàn)閐p[i][j]依賴dp[i1][j-1]必須保證內(nèi)層區(qū)間先被計(jì)算因此需要從右下角向左上角推進(jìn)j 的起點(diǎn)j從i開(kāi)始只計(jì)算j i的區(qū)間無(wú)需初始化對(duì)角線和無(wú)效區(qū)域答案維護(hù)每發(fā)現(xiàn)一個(gè)dp[i][j]為真就與當(dāng)前res比較長(zhǎng)度最終返回最長(zhǎng)回文子串。原文檔明確指出此方法的時(shí)間復(fù)雜度 O(n2)、空間復(fù)雜度 O(n2)——空間開(kāi)銷主要來(lái)自dp二維布爾表這是后續(xù)幾種解法優(yōu)化的起點(diǎn)。解法三中心擴(kuò)散法O(n2) / O(1)思路找到軸心向兩側(cè)擴(kuò)散動(dòng)態(tài)規(guī)劃將任意起始、終止范圍內(nèi)的字符串都判斷了一遍其實(shí)沒(méi)有這個(gè)必要——如果不是最長(zhǎng)回文串無(wú)需判斷并保存結(jié)果。因此動(dòng)態(tài)規(guī)劃在空間復(fù)雜度上仍有優(yōu)化空間。判斷回文有一個(gè)核心問(wèn)題是找到「軸心」如果回文串長(zhǎng)度是偶數(shù)軸心是中心虛擬的位于兩個(gè)字符之間如果長(zhǎng)度是奇數(shù)軸心正好是正中心的那個(gè)字母。中心擴(kuò)散法的思想是枚舉每個(gè)軸心的位置然后做兩次假設(shè)假設(shè)最長(zhǎng)回文串是偶數(shù)以虛擬中心往兩邊擴(kuò)散假設(shè)最長(zhǎng)回文串是奇數(shù)以正中心的字符往兩邊擴(kuò)散。擴(kuò)散的過(guò)程就是對(duì)稱判斷兩邊字符是否相等的過(guò)程。該方法時(shí)間復(fù)雜度與動(dòng)態(tài)規(guī)劃相同O(n2)但空間復(fù)雜度降低到 O(1)。Go 實(shí)現(xiàn)解析倉(cāng)庫(kù)中l(wèi)ongestPalindrome2與輔助函數(shù)maxPalindrome實(shí)現(xiàn)如下// 解法三 中心擴(kuò)散法時(shí)間復(fù)雜度 O(n^2)空間復(fù)雜度 O(1) func longestPalindrome2(s string) string { res : for i : 0; i len(s); i { res maxPalindrome(s, i, i, res) res maxPalindrome(s, i, i1, res) } return res } func maxPalindrome(s string, i, j int, res string) string { sub : for i 0 j len(s) s[i] s[j] { sub s[i : j1] i-- j } if len(res) len(sub) { return sub } return res }實(shí)現(xiàn)要點(diǎn)對(duì)每個(gè)下標(biāo)i分別以(i, i)奇數(shù)中心和(i, i1)偶數(shù)中心為軸心調(diào)用maxPalindromemaxPalindrome從中心向兩邊對(duì)稱擴(kuò)展條件不滿足越界或字符不等時(shí)退出返回值與當(dāng)前最優(yōu)res比較長(zhǎng)度始終維護(hù)最長(zhǎng)結(jié)果。這種寫(xiě)法沒(méi)有額外的數(shù)組空間復(fù)雜度 O(1)是面試中最容易現(xiàn)場(chǎng)寫(xiě)出的解法之一。解法二滑動(dòng)窗口O(n2) / O(1)思路中心擴(kuò)散的另一種寫(xiě)法原文檔指出滑動(dòng)窗口寫(xiě)法本質(zhì)上是中心擴(kuò)散法換了種寫(xiě)法。中心擴(kuò)散是依次枚舉每一個(gè)軸心滑動(dòng)窗口方法稍作優(yōu)化——有些軸心兩邊字符不相等下次就不會(huì)再枚舉這些不可能形成回文子串的軸心。但這點(diǎn)優(yōu)化并未改變時(shí)間復(fù)雜度仍是 O(n2)空間復(fù)雜度 O(1)。Go 實(shí)現(xiàn)解析倉(cāng)庫(kù)中l(wèi)ongestPalindrome1實(shí)現(xiàn)如下// 解法二 滑動(dòng)窗口時(shí)間復(fù)雜度 O(n^2)空間復(fù)雜度 O(1) func longestPalindrome1(s string) string { if len(s) 0 { return } left, right, pl, pr : 0, -1, 0, 0 for left len(s) { // 移動(dòng)到相同字母的最右邊如果有相同字母 for right1 len(s) s[left] s[right1] { right } // 找到回文的邊界 for left-1 0 right1 len(s) s[left-1] s[right1] { left-- right } if right-left pr-pl { pl, pr left, right } // 重置到下一次尋找回文的中心 left (leftright)/2 1 right left } return s[pl : pr1] }實(shí)現(xiàn)要點(diǎn)合并相同字符第一個(gè)內(nèi)層循環(huán)先把right推到與s[left]相同的最右位置一次性跳過(guò)連續(xù)的相同字母——這對(duì)應(yīng)「軸心可以是一段相同字符的區(qū)間」的觀察向外擴(kuò)散第二個(gè)內(nèi)層循環(huán)從該區(qū)間的兩側(cè)對(duì)稱擴(kuò)展找出以該連續(xù)區(qū)間為中心的最長(zhǎng)回文記錄并重置用pl、pr記錄全局最長(zhǎng)區(qū)間結(jié)束后把left重置為(leftright)/2 1即當(dāng)前回文中心右側(cè)的下一個(gè)位置right同步重置保證不重復(fù)枚舉已被判定的軸心區(qū)間邊界處理對(duì)空串直接返回此分支在測(cè)試用例中也被覆蓋。這種寫(xiě)法通過(guò)「相同字符區(qū)間」合并優(yōu)化了枚舉粒度是中心擴(kuò)散思想的一種工程化變體。解法一Manacher 馬拉車算法O(n) / O(n)為什么要做預(yù)處理統(tǒng)一奇偶原文檔指出中心擴(kuò)散法有 2 處重復(fù)判斷每次都往兩邊擴(kuò)散不同中心擴(kuò)散多次實(shí)際上有很多重復(fù)判斷的字符——能否不重復(fù)判斷中心能否跳躍選擇而不是每次都枚舉——是否可以利用前一次的信息跳躍選擇下一次的中心馬拉車算法正是針對(duì)這兩處重復(fù)判斷做了優(yōu)化增加一個(gè)輔助數(shù)組將時(shí)間復(fù)雜度從 O(n2) 優(yōu)化到 O(n)以空間換時(shí)間空間復(fù)雜度增加到 O(n)。預(yù)處理向字符串的頭尾以及每?jī)蓚€(gè)字符中間添加一個(gè)特殊字符#。例如字符串a(chǎn)aba處理后會(huì)變成#a#a#b#a#原先長(zhǎng)度為偶數(shù)的回文串a(chǎn)a會(huì)變成奇數(shù)長(zhǎng)度的#a#a#原先長(zhǎng)度為奇數(shù)的回文串a(chǎn)ba會(huì)變成仍為奇數(shù)長(zhǎng)度的#a#b#a#。經(jīng)過(guò)預(yù)處理后所有回文串都統(tǒng)一為奇數(shù)長(zhǎng)度從而只需處理一種中心情況。一個(gè)值得注意的細(xì)節(jié)原文檔特別強(qiáng)調(diào)這里的特殊字符不需要是沒(méi)有出現(xiàn)過(guò)的字母任意字符都可以作為特殊字符。原因在于當(dāng)只考慮奇數(shù)長(zhǎng)度的回文串時(shí)每次比較的兩個(gè)字符奇偶性一定相同所以原字符串中的字符不會(huì)與插入的特殊字符互相比較不會(huì)因此產(chǎn)生問(wèn)題。另一個(gè)關(guān)鍵結(jié)論預(yù)處理以后以某個(gè)中心擴(kuò)散的步數(shù)和實(shí)際字符串長(zhǎng)度相等。因?yàn)榘霃嚼锇瞬迦氲奶厥庾址钟捎谧笥覍?duì)稱的性質(zhì)擴(kuò)散半徑就等于原來(lái)回文子串的長(zhǎng)度。核心遞推dp[i] min(maxRight-i, dp[2*center-i])原文檔給出了核心部分的推理。定義下一次要擴(kuò)散的中心下標(biāo)為i如果i比maxRight大嚴(yán)格說(shuō)是i maxRight無(wú)法利用已有信息只能繼續(xù)中心擴(kuò)散如果i比maxRight小此時(shí)i落在已知回文區(qū)間[center - dp[center], center dp[center]]內(nèi)可借助與i關(guān)于center對(duì)稱的鏡像點(diǎn)mirror 2*center - i的已知半徑來(lái)初始化dp[i]。將上述情況總結(jié)起來(lái)就是核心公式dp[i] min(maxRight-i, dp[2*center-i])其中mirror相對(duì)于center與i中心對(duì)稱下標(biāo)為2*center-i。更新完dp[i]以后進(jìn)行中心擴(kuò)散擴(kuò)散后動(dòng)態(tài)維護(hù)最長(zhǎng)回文串并相應(yīng)更新center、maxRight同時(shí)記錄原始字符串中的起始位置begin和最大半徑maxLen。Go 實(shí)現(xiàn)解析倉(cāng)庫(kù)中l(wèi)ongestPalindromeManacher 主函數(shù)與輔助函數(shù)min實(shí)現(xiàn)如下// 解法一 Manachers algorithm時(shí)間復(fù)雜度 O(n)空間復(fù)雜度 O(n) func longestPalindrome(s string) string { if len(s) 2 { return s } newS : make([]rune, 0) newS append(newS, #) for _, c : range s { newS append(newS, c) newS append(newS, #) } // dp[i]: 以預(yù)處理字符串下標(biāo) i 為中心的回文半徑(奇數(shù)長(zhǎng)度時(shí)不包括中心) // maxRight: 通過(guò)中心擴(kuò)散的方式能夠擴(kuò)散的最右邊的下標(biāo) // center: 與 maxRight 對(duì)應(yīng)的中心字符的下標(biāo) // maxLen: 記錄最長(zhǎng)回文串的半徑 // begin: 記錄最長(zhǎng)回文串在起始串 s 中的起始下標(biāo) dp, maxRight, center, maxLen, begin : make([]int, len(newS)), 0, 0, 1, 0 for i : 0; i len(newS); i { if i maxRight { // 這一行代碼是 Manacher 算法的關(guān)鍵所在 dp[i] min(maxRight-i, dp[2*center-i]) } // 中心擴(kuò)散法更新 dp[i] left, right : i-(1dp[i]), i(1dp[i]) for left 0 right len(newS) newS[left] newS[right] { dp[i] left-- right } // 更新 maxRight它是遍歷過(guò)的 i 的 i dp[i] 的最大者 if idp[i] maxRight { maxRight i dp[i] center i } // 記錄最長(zhǎng)回文子串的長(zhǎng)度和相應(yīng)它在原始字符串中的起點(diǎn) if dp[i] maxLen { maxLen dp[i] begin (i - maxLen) / 2 // 這里要除以 2 因?yàn)橛形覀儾迦氲妮o助字符 # } } return s[begin : beginmaxLen] } func min(x, y int) int { if x y { return x } return y }分步解讀預(yù)處理用[]rune構(gòu)建#與原字符交替的newS。注意使用rune切片而非byte可正確處理多字節(jié)字符避免下標(biāo)錯(cuò)位變量語(yǔ)義dp[i]為以i為中心的回文半徑奇數(shù)長(zhǎng)度時(shí)不含中心本身maxRight是已遍歷過(guò)中心中能擴(kuò)散到的最右下標(biāo)center是與maxRight對(duì)應(yīng)的中心maxLen、begin記錄最優(yōu)答案對(duì)稱性初始化if i maxRight時(shí)用min(maxRight-i, dp[2*center-i])直接給dp[i]一個(gè)下界這是整個(gè)算法不重復(fù)判斷的關(guān)鍵一行中心擴(kuò)散補(bǔ)全left, right : i-(1dp[i]), i(1dp[i])從已確認(rèn)的半徑外一格外開(kāi)始比對(duì)循環(huán)內(nèi)對(duì)稱字符相等則dp[i]并繼續(xù)外擴(kuò)動(dòng)態(tài)維護(hù)每次擴(kuò)散完若idp[i] maxRight則更新maxRight與center若dp[i] maxLen則更新maxLen和begin坐標(biāo)還原begin (i - maxLen) / 2需要除以 2因?yàn)轭A(yù)處理字符串中插入了輔助字符#最后返回s[begin : beginmaxLen]即為原始字符串中的最長(zhǎng)回文子串。該解法時(shí)間 O(n)每個(gè)字符的擴(kuò)散總次數(shù)受maxRight單調(diào)推進(jìn)約束、空間 O(n)dp數(shù)組是本題的最優(yōu)解也是四種解法中最復(fù)雜的。測(cè)試驗(yàn)證四種解法如何被同時(shí)驗(yàn)證本倉(cāng)庫(kù)對(duì)每道題都配有獨(dú)立的_test.go測(cè)試文件。5. Longest Palindromic Substring_test.go 中的Test_Problem5定義了如下測(cè)試用例輸入s期望輸出babadbabcbbdbbaaacaaaaa一段 200 字符的長(zhǎng)字符串與輸入完全相同整個(gè)串本身即為回文測(cè)試用例覆蓋了奇數(shù)回文、偶數(shù)回文、單字符、雙字符、空串、以及整串回文最長(zhǎng)邊界等典型場(chǎng)景。值得關(guān)注的是用例組織方式每一條用例的答案都被同時(shí)傳入四個(gè)函數(shù)并打印對(duì)比f(wàn)mt.Printf(【input】:%v 【output】:%v %v %v %v\n, p, longestPalindrome(p.s), longestPalindrome1(p.s), longestPalindrome2(p.s), longestPalindrome3(p.s))這意味著一組測(cè)試輸入同時(shí)校驗(yàn) Manacher、滑動(dòng)窗口、中心擴(kuò)散、DP 四種實(shí)現(xiàn)的輸出是否一致任何一版實(shí)現(xiàn)回歸出錯(cuò)都會(huì)被立即發(fā)現(xiàn)。從代碼結(jié)構(gòu)看測(cè)試以fmt.Printf打印四種解法輸出供人工比對(duì)倉(cāng)庫(kù)根目錄的 gotest.sh 腳本則統(tǒng)一通過(guò)go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...對(duì)整個(gè)leetcode包生成覆蓋率報(bào)告與本倉(cāng)庫(kù)「100% test coverage」的目標(biāo)一致詳見(jiàn) README.md。若要在本地驗(yàn)證本題可以進(jìn)入倉(cāng)庫(kù)根目錄執(zhí)行g(shù)o test -v -run Test_Problem5 ./leetcode/0005.Longest-Palindromic-Substring/四種解法對(duì)比總結(jié)與選型建議從原文檔與源碼實(shí)現(xiàn)可以提煉出如下選型建議面試首推中心擴(kuò)散法解法三。代碼最短、思路直觀、空間 O(1)易于在面試中現(xiàn)場(chǎng)推導(dǎo)和書(shū)寫(xiě)需要最優(yōu)解Manacher 算法解法一。當(dāng)n很大如本倉(cāng)庫(kù)測(cè)試中長(zhǎng)達(dá) 200 字符的回文串且對(duì)時(shí)間復(fù)雜度敏感時(shí)O(n) 線性復(fù)雜度是唯一選擇但實(shí)現(xiàn)細(xì)節(jié)多、不易一次寫(xiě)對(duì)適合作為進(jìn)階知識(shí)點(diǎn)掌握理解 DP 基礎(chǔ)動(dòng)態(tài)規(guī)劃解法四雖空間開(kāi)銷大但狀態(tài)轉(zhuǎn)移方程是理解回文子串結(jié)構(gòu)的最佳入門也是很多區(qū)間 DP 問(wèn)題的通用模板工程化變體滑動(dòng)窗口解法二通過(guò)合并相同字符區(qū)間減少枚舉展示了對(duì)中心擴(kuò)散的優(yōu)化思路空間同樣 O(1)。這四種解法完整覆蓋了「從樸素到最優(yōu)」的演進(jìn)路徑是理解回文串類問(wèn)題的絕佳范例。讀者可對(duì)照倉(cāng)庫(kù)中的 題解文檔、源碼 與 測(cè)試用例 三者聯(lián)動(dòng)研讀形成完整的「題目 → 思路 → 實(shí)現(xiàn) → 驗(yàn)證」閉環(huán)?！久赓M(fèi)下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項(xiàng)目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考