去面試過開發(fā)崗的人應(yīng)該都有這種體會(huì)筆試環(huán)節(jié)時(shí)間緊、題量大第一題往往不是最難的但一定是最考驗(yàn)基本功的。“最短回文串的變體”這類題目我在不同公司的筆試題里見過至少三四回幾乎每次都有考生在邊界條件和變體處理上翻車。這道題核心是字符串處理但展開之后能串起 KMP、Manacher、動(dòng)態(tài)規(guī)劃、哈希這些高頻考點(diǎn)屬于典型的“一題多解、一題多面”的題目。我先把題目描述還原一下給定一個(gè)字符串 s允許在指定位置插入字符把它變成回文串問最終得到的最短長(zhǎng)度是多少或者要求構(gòu)造出最短回文串。經(jīng)典版本是“只允許在頭部插入字符”而“變體”兩個(gè)字意味著題目可能改成了尾部插入、兩端插入、任意位置插入甚至要求統(tǒng)計(jì)不同方案數(shù)。這篇文章就把這些變體一網(wǎng)打盡從思路推導(dǎo)到代碼實(shí)現(xiàn)再到筆試時(shí)的答題技巧全部說透。1. 問題拆解與考點(diǎn)定位變體到底在變什么1.1 先吃透經(jīng)典版最短回文串的原始模型LeetCode 上著名的 214 題就是最短回文串的經(jīng)典版本給定一個(gè)字符串 s你只能在它的最前面添加字符使得結(jié)果是一個(gè)回文串問能得到的長(zhǎng)度最短的結(jié)果是什么。比如輸入s aacecaaa答案是aaacecaaa只插入了一個(gè)a。這個(gè)問題的本質(zhì)是找s的“最長(zhǎng)回文前綴”。為什么是前綴因?yàn)樵陬^部插入字符時(shí)插入的那些字符其實(shí)就是把原字符串前半段缺掉的部分補(bǔ)齊最終結(jié)果會(huì)保留原始字符串的“尾部結(jié)構(gòu)”。舉個(gè)例子s abcb最長(zhǎng)回文前綴是abcba嗎不是abcb的最長(zhǎng)回文前綴是a或abcbaabcba并不存在因?yàn)樵疀]有a在末尾。正確的最長(zhǎng)回文前綴是a所以需要在頭部補(bǔ)上bcb最終得到bcbabcb不對(duì)我們驗(yàn)證一下在頭部加上bcb得到bcbabcb這個(gè)串是bcb a bcb原串a(chǎn)bcb補(bǔ)bcb后是bcb a b c b寫成bcbabcb它是回文b-c-b-a-b-c-b正反一致成立。這里的關(guān)鍵是從頭部補(bǔ)最終結(jié)果等于“某個(gè)回文后綴的前綴部分的鏡像”從 KMP 角度理解會(huì)更透徹。這也是面試官最愛追問的點(diǎn)你能不能證明補(bǔ)全的字符數(shù)等于原串長(zhǎng)度減去最長(zhǎng)回文前綴的長(zhǎng)度。1.2 變體方向的常見劃分在筆試環(huán)境下“最短回文串的變體”通常有幾種改法變體 A只允許在尾部插入字符。思路完全對(duì)稱找“最長(zhǎng)回文后綴”。變體 B允許在頭部和尾部同時(shí)插入字符。這種題等價(jià)于找原串的一個(gè)“中心回文子串”然后向兩側(cè)補(bǔ)齊。變體 C允許在任意位置插入字符。這就變成了經(jīng)典的“插入最少字符構(gòu)造回文串”屬于區(qū)間 DP 的范疇。變體 D要求輸出所有不同方案或統(tǒng)計(jì)方案數(shù)量。在 DP 基礎(chǔ)上加計(jì)數(shù)復(fù)雜度不變但細(xì)節(jié)爆炸。不同變體對(duì)應(yīng)的算法完全不同只要你把題目限定條件看清楚區(qū)分度立刻出來了。很多考生失分不是因?yàn)椴粫?huì)算法而是沒看清到底讓從哪頭插。2. 經(jīng)典解法深挖KMP 與雙指針兩種路線2.1 解法一反轉(zhuǎn)字符串 KMP next 表這個(gè)方法我強(qiáng)烈建議每個(gè)人都要能默寫。思路是把原串 s 反轉(zhuǎn)得到 rev_s然后構(gòu)造一個(gè)臨時(shí)串t s # rev_s。中間的分隔符必須是原串中不會(huì)出現(xiàn)的字符目的是防止前綴跨過拼接邊界產(chǎn)生“假匹配”。求t的 next 數(shù)組有些資料叫前綴函數(shù) prefix function最后一個(gè) next 值表示t的最長(zhǎng)相等前后綴長(zhǎng)度。由于t的前半部分是 s、后半部分是反轉(zhuǎn)后的 s這個(gè)最長(zhǎng)相等前后綴恰好對(duì)應(yīng) s 的最長(zhǎng)回文前綴的長(zhǎng)度。于是頭部需要插入的字符數(shù)就是n - next.back()。C 參考實(shí)現(xiàn)string shortestPalindromeFront(string s) { string rev s; reverse(rev.begin(), rev.end()); string t s # rev; int n t.size(); vectorint next(n, 0); for (int i 1; i n; i) { int j next[i - 1]; while (j 0 t[i] ! t[j]) j next[j - 1]; if (t[i] t[j]) j; next[i] j; } int len next[n - 1]; // 最長(zhǎng)回文前綴長(zhǎng)度 string add s.substr(len); // 剩余后綴 reverse(add.begin(), add.end()); return add s; }復(fù)雜度是 O(n)筆試時(shí)這是最優(yōu)級(jí)別的解法。為什么分隔符用#不用的話如果s aaaat aaaa aaaa最后 next 值會(huì)變成 7明顯越界顯然不對(duì)。加了#后將匹配邊界隔斷next 值不會(huì)超過 n。這是很多人在默寫時(shí)最容易忽略的細(xì)節(jié)。2.2 解法二雙指針貪心 遞歸如果不追求 O(n)可以這樣想從左右兩端開始檢查找到最長(zhǎng)的回文前綴。每找到一對(duì)相等的字符就向內(nèi)收縮一旦不相等說明當(dāng)前這層不是回文需要把最右側(cè)的字符補(bǔ)到左邊。這個(gè)過程天然適合遞歸。shortestPalindrome(s)的遞歸式如果s本身就是回文直接返回。找到第一個(gè)使s[0..i]為回文的最大i此時(shí)s[0..i]是回文前綴。把s[i1..n-1]的逆序加到 s 前面然后繼續(xù)遞歸處理沒對(duì)齊的部分。實(shí)際上這個(gè)“遞歸處理”可以簡(jiǎn)化因?yàn)橛疫吺Ｏ碌牟糠中枰麄€(gè)反轉(zhuǎn)到左邊遞歸只需要處理中間段。實(shí)現(xiàn)如下string helper(string s) { int n s.size(); if (n 0) return ; int i 0; for (int j n - 1; j 0; j--) { if (s[i] s[j]) i; } if (i n) return s; // 整個(gè)串已經(jīng)是回文 // i 是第一次失配的邊界剩下部分需要遞歸 string remain s.substr(i); string rev remain; reverse(rev.begin(), rev.end()); return rev helper(s.substr(0, i)) remain; }這個(gè)解法比 KMP 好理解但最壞情況是 O(n2)。比如s是由前面一堆無關(guān)字符加尾部一個(gè)長(zhǎng)回文構(gòu)成的每次遞歸只消除一個(gè)字符。筆試時(shí)如果數(shù)據(jù)范圍是n 10^5這解法會(huì)超時(shí)建議只用來做思考題或在面試時(shí)展示思路不建議作為最終提交版本。2.3 為什么筆試更偏愛 KMP 路線以我批改模擬題的經(jīng)驗(yàn)來看這道題放在第一題數(shù)據(jù)范圍大概率是10^5到10^6暴力雙指針即使能跑對(duì)也過不了大數(shù)據(jù)測(cè)試點(diǎn)。而 KMP next 表的方法代碼量少、思路固定、復(fù)雜度可控是性價(jià)比最高的選擇。另一個(gè) O(n) 方案是 Manacher 算法下面單獨(dú)講。3. 變體 A/B尾部插入與兩端插入的對(duì)稱思路3.1 尾部插入找最長(zhǎng)回文后綴如果題目說“只能在尾部插入”你不需要另想新算法只需把原串反轉(zhuǎn)用同樣的 KMP 邏輯處理。具體做法是t rev_s # s最后一個(gè) next 值表示的最長(zhǎng)相等前后綴正好對(duì)應(yīng) s 的最長(zhǎng)回文后綴的長(zhǎng)度。需要補(bǔ)全的部分是前綴去掉最長(zhǎng)回文后綴的部分把這段逆序接在尾部。string shortestPalindromeBack(string s) { string rev s; reverse(rev.begin(), rev.end()); string t rev # s; int n t.size(); vectorint next(n, 0); for (int i 1; i n; i) { int j next[i - 1]; while (j 0 t[i] ! t[j]) j next[j - 1]; if (t[i] t[j]) j; next[i] j; } int len next[n - 1]; // 最長(zhǎng)回文后綴 string add s.substr(0, s.size() - len); reverse(add.begin(), add.end()); return s add; }這里有個(gè)容易繞暈的點(diǎn)為什么尾部插入時(shí) tp 的拼接順序是rev # s因?yàn)槲覀冃枰氖恰皊 的某個(gè)后綴”作為一個(gè)整體回文而這個(gè)后綴在反轉(zhuǎn)后的串里剛好對(duì)應(yīng)前綴。KMP next 值要求的是前綴等于后綴對(duì)調(diào)拼接順序才能讓這兩個(gè)概念對(duì)上。建議你拿s abb手動(dòng)推一遍最長(zhǎng)回文后綴是bb補(bǔ)一個(gè)a到尾部得到abba。3.2 兩端插入找最長(zhǎng)的“中心回文”如果題目允許頭尾都插入但每次只能在兩端補(bǔ)字符這時(shí)候最終結(jié)果的中心一定來自原串中的某個(gè)回文子串并且這個(gè)子串要盡可能長(zhǎng)。因?yàn)槟悴迦氲淖址际菄@中心對(duì)稱補(bǔ)上去的中心越長(zhǎng)需要補(bǔ)的越少。判斷標(biāo)準(zhǔn)對(duì)原串的每個(gè)位置 i求出以 i 為中心的最長(zhǎng)奇數(shù)長(zhǎng)度回文、以 i 和 i1 之間為中心的最長(zhǎng)偶數(shù)長(zhǎng)度回文如果這個(gè)回文子串能“觸達(dá)”原串的某一端就說明從該端開始已經(jīng)天然對(duì)稱只需要在另一端補(bǔ)齊剩余部分。用 Manacher 算法可以在 O(n) 內(nèi)求出所有回文半徑。之后對(duì)每個(gè)中心檢查回文子串是否覆蓋左邊界或右邊界如果覆蓋左邊界說明左側(cè)已經(jīng)對(duì)稱需要在尾部補(bǔ)右側(cè)剩余部分的逆序。如果覆蓋右邊界說明右側(cè)已經(jīng)對(duì)稱需要在頭部補(bǔ)左側(cè)剩余部分的逆序。兩種情況取補(bǔ)全后總長(zhǎng)度更小的那個(gè)。3.3 Manacher 在筆試題里的適用度Manacher 雖然比 KMP 冷門但在“求最長(zhǎng)回文子串”的題目里是標(biāo)準(zhǔn)解法。如果你對(duì) Manacher 的半徑擴(kuò)展和對(duì)稱性利用不夠熟考場(chǎng)上一旦寫錯(cuò)一個(gè)下標(biāo)調(diào)試代價(jià)很高。我個(gè)人建議如果變體題目明確說“兩端插入”或者“找最長(zhǎng)中心回文”優(yōu)先用 Manacher如果只是“頭部插入”的經(jīng)典題KMP 足夠。Manacher 的關(guān)鍵是把原始串每個(gè)字符之間插入#統(tǒng)一奇偶長(zhǎng)度。回文半徑數(shù)組p[i]表示以 i 為中心、包含中心字符在內(nèi)的擴(kuò)展半徑最終回文長(zhǎng)度是p[i] - 1。這個(gè)細(xì)節(jié)我后面在測(cè)試用例部分還會(huì)提到。4. 變體 C 的完整攻略任意位置插入的最少次數(shù)4.1 變成區(qū)間 DP 模型如果題目改成“可以在任意位置插入字符”那就完全換了一個(gè)類型本質(zhì)是求把一個(gè)字符串變成回文串的最少插入字符數(shù)。這是個(gè)非常經(jīng)典的二維動(dòng)態(tài)規(guī)劃問題。定義狀態(tài)dp[i][j]表示把子串s[i..j]變成回文串所需的最少插入次數(shù)。轉(zhuǎn)移分為兩種情況如果s[i] s[j]兩端已經(jīng)匹配dp[i][j] dp[i1][j-1]。否則要么在右邊插入一個(gè)與s[i]相等的字符去匹配左端要么在左邊插入一個(gè)與s[j]相等的字符去匹配右端取兩者較小值即1 min(dp[i1][j], dp[i][j-1])。最終答案是dp[0][n-1]。4.2 最小插入次數(shù)的完整實(shí)現(xiàn)int minInsertions(string s) { int n s.size(); vectorvectorint dp(n, vectorint(n, 0)); for (int len 2; len n; len) { for (int i 0; i len - 1 n; i) { int j i len - 1; if (s[i] s[j]) { dp[i][j] dp[i 1][j - 1]; } else { dp[i][j] 1 min(dp[i 1][j], dp[i][j - 1]); } } } return dp[0][n - 1]; }注意循環(huán)順序必須按照區(qū)間長(zhǎng)度從小到大。因?yàn)橛?jì)算長(zhǎng)區(qū)間需要依賴更短區(qū)間的結(jié)果如果直接枚舉 i、j很可能某個(gè)dp[i1][j-1]還沒算出來。這是區(qū)間 DP 最常見的坑。4.3 把“次數(shù)”升級(jí)成“方案數(shù)”變體還可能要求統(tǒng)計(jì)“有多少種不同的最短插入方案”。這需要在 DP 過程中同步維護(hù)方案數(shù)。定義ways[i][j]表示達(dá)到dp[i][j]最小次數(shù)的方案數(shù)。轉(zhuǎn)移時(shí)s[i] s[j]方案數(shù)等于內(nèi)部子串的方案數(shù)。s[i] ! s[j]如果dp[i1][j] dp[i][j-1]則方案數(shù)繼承ways[i1][j]反之繼承ways[i][j-1]如果兩者相等方案數(shù)相加。這里要注意當(dāng)兩端不相等時(shí)實(shí)際插入位置不同會(huì)導(dǎo)致結(jié)果不同但計(jì)數(shù)模型只需關(guān)注“選擇”的路徑。如果題目還要求去重情況會(huì)復(fù)雜一些通常需要引入字符串哈?；蛘邩?gòu)造自動(dòng)機(jī)筆試一般不會(huì)考到那么深。真遇到的話先寫樸素 DP 拿部分分再考慮優(yōu)化。5. 筆試實(shí)戰(zhàn)中的高頻坑與測(cè)試用例清單5.1 邊界條件十個(gè)必須過的用例我在模擬面試時(shí)經(jīng)常拿下面這組用例檢驗(yàn)候選人的實(shí)現(xiàn)這里直接分享出來輸入頭部插入答案說明空串很多人忘記判空aa單字符天然回文aaaa雙字符回文abbab最長(zhǎng)回文前綴是aabaaba整體回文不需要補(bǔ)abccbabc只有第一個(gè)字符是回文前綴aabbaab最長(zhǎng)回文前綴是aaabbbbabb最長(zhǎng)回文前綴是a實(shí)際手工推一下aaaaaaaa全同字符注意 KMP 分隔符abaccabac最長(zhǎng)回文前綴aba第 8 個(gè)用例值得多說一句s abb最長(zhǎng)回文前綴是a補(bǔ)bb到頭部得到bbabb。如果用反轉(zhuǎn)字符串拼接 KMP 的做法t abb#bba最后一個(gè) next 值是 1對(duì)應(yīng)a正確。如果你算出來答案是bbabb但中間過程對(duì)不上多半是 next 數(shù)組初始化或下標(biāo)更新出了偏差。5.2 重現(xiàn)的經(jīng)典翻車現(xiàn)場(chǎng)常見的錯(cuò)誤有四種。第一KMP 的 next 數(shù)組循環(huán)寫成for (int i 0; i n; i)而不是從 1 開始。next[0]一定初始化為 0否則首個(gè)字符比較邏輯全亂。第二拼接臨時(shí)串時(shí)忘記加分隔符。s aaaa的情況不加分隔符會(huì)得到虛假的重疊匹配直接導(dǎo)致輸出多出幾個(gè)字符。分隔符一定要選原串中不存在的字符筆試時(shí)通常用#但如果輸入本身就含#就要換或$。穩(wěn)妥做法是再加一個(gè)判斷或者用 platform 不出現(xiàn)的 char實(shí)際競(jìng)賽里常用char(0)。第三對(duì)字符串長(zhǎng)度為奇偶時(shí)的回文中心判斷錯(cuò)誤。在 Manacher 方案里插入#之后所有回文都變奇數(shù)長(zhǎng)度回文半徑減一才是原串長(zhǎng)度這一步經(jīng)常有人多減或少減。第四使用遞歸方案時(shí)遞歸深度過大導(dǎo)致棧溢出。雖然 O(n2) 超時(shí)已經(jīng)是硬傷但有些考生在自測(cè)小數(shù)據(jù)時(shí)又因?yàn)檫f歸寫法爆棧連部分分都拿不到。如果面試要求寫一個(gè)“能跑”的版本優(yōu)先寫迭代。5.3 筆試現(xiàn)場(chǎng)的答題策略我個(gè)人的建議是按這個(gè)順序分配時(shí)間拿到題目后先確認(rèn)變體類型。如果是頭部插入直接默寫 KMP 版本。如果是尾部插入把 KMP 版本對(duì)稱改動(dòng)。如果是兩端插入考慮 Manacher 但不要盲目使用先用最長(zhǎng)回文前綴的結(jié)論思考一下很多時(shí)候兩端插入的最優(yōu)解其實(shí)就是“從左邊找最長(zhǎng)回文前綴補(bǔ)右邊”和“從右邊找最長(zhǎng)回文后綴補(bǔ)左邊”二選一不一定真的需要 Manacher。只有任意位置插入才切換到區(qū)間 DP。做完基礎(chǔ)版本后立刻跑幾個(gè)邊界用例空串、單字符、全同字符、本身就是回文串、完全無重復(fù)字符。這五個(gè)用例基本能覆蓋九成邏輯錯(cuò)誤。6. 從這道題延展出的算法思維6.1 回文串題型的統(tǒng)一思考框架回文串問題在筆試中非常高頻從最簡(jiǎn)單的判斷回文到最長(zhǎng)回文子串、最長(zhǎng)回文子序列、最短回文串再到插入次數(shù)統(tǒng)計(jì)本質(zhì)都是在回答兩個(gè)問題回文的“中心”在哪回文的“覆蓋范圍”有多大。雙指針從兩邊往中間找適合判斷型問題。中心擴(kuò)展適合求最長(zhǎng)回文子串但最壞 O(n2)。Manacher 用對(duì)稱性加速中心擴(kuò)展是 O(n) 求最長(zhǎng)回文子串的標(biāo)準(zhǔn)答案。KMP next 表擅長(zhǎng)解決“前綴和后綴匹配”的問題所以它能直接套用到頭部或尾部插入。區(qū)間 DP 適合“允許內(nèi)部修改”的構(gòu)造型問題。面試官如果繼續(xù)追問“能不能優(yōu)化到 O(n log n)”你還可以提到二分 字符串哈希枚舉回文半徑時(shí)用哈?？焖倥袛嘧笥覂蓚?cè)是否相等。這個(gè)思路在做后綴數(shù)組題時(shí)也經(jīng)常用到掌握它相當(dāng)于多了一把鑰匙。6.2 一題多解背后的出題意圖“最短回文串的變體”之所以被放在第一題我理解出題人想考察的是候選人有沒有形成一套完整的字符串算法工具箱。第一題不會(huì)故意為難你但如果你連“變體”和“經(jīng)典題”的差異都看不出來或者只背了 LeetCode 原題代碼、遇到改動(dòng)就無從下手那基本就被淘汰了。這種題的答題表現(xiàn)往往能直接反映一個(gè)人的刷題方式。只會(huì)背題解的人寫出來的代碼結(jié)構(gòu)死板邊界變量命名混亂容易在變體類型切換時(shí)迷路。真正理解原理的人可以三分鐘內(nèi)把 KMP 版本改造成尾部插入版本。6.3 后續(xù)擴(kuò)展方向如果你還想繼續(xù)深挖可以試著做這幾個(gè)練習(xí)輸出具體的最短回文串而不是長(zhǎng)度要求對(duì)多種方案去重。將任意位置插入的最小次數(shù)問題改成“最少刪除幾個(gè)字符可以變成回文串”等價(jià)變換為“最長(zhǎng)回文子序列長(zhǎng)度”。用二分 字符串哈希重寫頭部插入版本對(duì)比 KMP 版本在常數(shù)和可讀性上的差異。在區(qū)間 DP 版本里加入滾動(dòng)數(shù)組把空間復(fù)雜度從 O(n2) 降到 O(n)。我在實(shí)際工作中處理日志數(shù)據(jù)清洗時(shí)遇到過“給一串缺失引號(hào)的內(nèi)容自動(dòng)補(bǔ)全成合法對(duì)稱結(jié)構(gòu)”的需求底層思路就和這道題完全一致。字符串算法的價(jià)值不在炫技而是當(dāng)數(shù)據(jù)形狀不對(duì)時(shí)你能快速判斷出該用哪種拼接策略。我個(gè)人在考場(chǎng)上最深的體會(huì)是不要急著寫代碼先用三分鐘把變體類型標(biāo)在草稿紙上寫出狀態(tài)定義或者匹配關(guān)系再動(dòng)手。代碼只是最后一步的翻譯工作思路清晰了代碼基本不會(huì)錯(cuò)。這道題覆蓋的 KMP、Manacher、區(qū)間 DP 三個(gè)核心工具值得你反復(fù)練習(xí)到下意識(shí)就能寫出來。下次不管它怎么變只要看到“回文串”“插入字符”“最短”這幾個(gè)關(guān)鍵詞你能第一時(shí)間鎖定正確的算法族這道題就拿下了。