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