去面试过开发岗的人应该都有这种体会笔试环节时间紧、题量大第一题往往不是最难的但一定是最考验基本功的。“最短回文串的变体”这类题目我在不同公司的笔试题里见过至少三四回几乎每次都有考生在边界条件和变体处理上翻车。这道题核心是字符串处理但展开之后能串起 KMP、Manacher、动态规划、哈希这些高频考点属于典型的“一题多解、一题多面”的题目。我先把题目描述还原一下给定一个字符串 s允许在指定位置插入字符把它变成回文串问最终得到的最短长度是多少或者要求构造出最短回文串。经典版本是“只允许在头部插入字符”而“变体”两个字意味着题目可能改成了尾部插入、两端插入、任意位置插入甚至要求统计不同方案数。这篇文章就把这些变体一网打尽从思路推导到代码实现再到笔试时的答题技巧全部说透。1. 问题拆解与考点定位变体到底在变什么1.1 先吃透经典版最短回文串的原始模型LeetCode 上著名的 214 题就是最短回文串的经典版本给定一个字符串 s你只能在它的最前面添加字符使得结果是一个回文串问能得到的长度最短的结果是什么。比如输入s aacecaaa答案是aaacecaaa只插入了一个a。这个问题的本质是找s的“最长回文前缀”。为什么是前缀因为在头部插入字符时插入的那些字符其实就是把原字符串前半段缺掉的部分补齐最终结果会保留原始字符串的“尾部结构”。举个例子s abcb最长回文前缀是abcba吗不是abcb的最长回文前缀是a或abcbaabcba并不存在因为原串没有a在末尾。正确的最长回文前缀是a所以需要在头部补上bcb最终得到bcbabcb不对我们验证一下在头部加上bcb得到bcbabcb这个串是bcb a bcb原串abcb补bcb后是bcb a b c b写成bcbabcb它是回文b-c-b-a-b-c-b正反一致成立。这里的关键是从头部补最终结果等于“某个回文后缀的前缀部分的镜像”从 KMP 角度理解会更透彻。这也是面试官最爱追问的点你能不能证明补全的字符数等于原串长度减去最长回文前缀的长度。1.2 变体方向的常见划分在笔试环境下“最短回文串的变体”通常有几种改法变体 A只允许在尾部插入字符。思路完全对称找“最长回文后缀”。变体 B允许在头部和尾部同时插入字符。这种题等价于找原串的一个“中心回文子串”然后向两侧补齐。变体 C允许在任意位置插入字符。这就变成了经典的“插入最少字符构造回文串”属于区间 DP 的范畴。变体 D要求输出所有不同方案或统计方案数量。在 DP 基础上加计数复杂度不变但细节爆炸。不同变体对应的算法完全不同只要你把题目限定条件看清楚区分度立刻出来了。很多考生失分不是因为不会算法而是没看清到底让从哪头插。2. 经典解法深挖KMP 与双指针两种路线2.1 解法一反转字符串 KMP next 表这个方法我强烈建议每个人都要能默写。思路是把原串 s 反转得到 rev_s然后构造一个临时串t s # rev_s。中间的分隔符必须是原串中不会出现的字符目的是防止前缀跨过拼接边界产生“假匹配”。求t的 next 数组有些资料叫前缀函数 prefix function最后一个 next 值表示t的最长相等前后缀长度。由于t的前半部分是 s、后半部分是反转后的 s这个最长相等前后缀恰好对应 s 的最长回文前缀的长度。于是头部需要插入的字符数就是n - next.back()。C 参考实现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)笔试时这是最优级别的解法。为什么分隔符用#不用的话如果s aaaat aaaa aaaa最后 next 值会变成 7明显越界显然不对。加了#后将匹配边界隔断next 值不会超过 n。这是很多人在默写时最容易忽略的细节。2.2 解法二双指针贪心 递归如果不追求 O(n)可以这样想从左右两端开始检查找到最长的回文前缀。每找到一对相等的字符就向内收缩一旦不相等说明当前这层不是回文需要把最右侧的字符补到左边。这个过程天然适合递归。shortestPalindrome(s)的递归式如果s本身就是回文直接返回。找到第一个使s[0..i]为回文的最大i此时s[0..i]是回文前缀。把s[i1..n-1]的逆序加到 s 前面然后继续递归处理没对齐的部分。实际上这个“递归处理”可以简化因为右边剩下的部分需要整个反转到左边递归只需要处理中间段。实现如下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; // 整个串已经是回文 // i 是第一次失配的边界剩下部分需要递归 string remain s.substr(i); string rev remain; reverse(rev.begin(), rev.end()); return rev helper(s.substr(0, i)) remain; }这个解法比 KMP 好理解但最坏情况是 O(n²)。比如s是由前面一堆无关字符加尾部一个长回文构成的每次递归只消除一个字符。笔试时如果数据范围是n 10^5这解法会超时建议只用来做思考题或在面试时展示思路不建议作为最终提交版本。2.3 为什么笔试更偏爱 KMP 路线以我批改模拟题的经验来看这道题放在第一题数据范围大概率是10^5到10^6暴力双指针即使能跑对也过不了大数据测试点。而 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 值要求的是前缀等于后缀对调拼接顺序才能让这两个概念对上。建议你拿s abb手动推一遍最长回文后缀是bb补一个a到尾部得到abba。3.2 两端插入找最长的“中心回文”如果题目允许头尾都插入但每次只能在两端补字符这时候最终结果的中心一定来自原串中的某个回文子串并且这个子串要尽可能长。因为你插入的字符都是围绕中心对称补上去的中心越长需要补的越少。判断标准对原串的每个位置 i求出以 i 为中心的最长奇数长度回文、以 i 和 i1 之间为中心的最长偶数长度回文如果这个回文子串能“触达”原串的某一端就说明从该端开始已经天然对称只需要在另一端补齐剩余部分。用 Manacher 算法可以在 O(n) 内求出所有回文半径。之后对每个中心检查回文子串是否覆盖左边界或右边界如果覆盖左边界说明左侧已经对称需要在尾部补右侧剩余部分的逆序。如果覆盖右边界说明右侧已经对称需要在头部补左侧剩余部分的逆序。两种情况取补全后总长度更小的那个。3.3 Manacher 在笔试题里的适用度Manacher 虽然比 KMP 冷门但在“求最长回文子串”的题目里是标准解法。如果你对 Manacher 的半径扩展和对称性利用不够熟考场上一旦写错一个下标调试代价很高。我个人建议如果变体题目明确说“两端插入”或者“找最长中心回文”优先用 Manacher如果只是“头部插入”的经典题KMP 足够。Manacher 的关键是把原始串每个字符之间插入#统一奇偶长度。回文半径数组p[i]表示以 i 为中心、包含中心字符在内的扩展半径最终回文长度是p[i] - 1。这个细节我后面在测试用例部分还会提到。4. 变体 C 的完整攻略任意位置插入的最少次数4.1 变成区间 DP 模型如果题目改成“可以在任意位置插入字符”那就完全换了一个类型本质是求把一个字符串变成回文串的最少插入字符数。这是个非常经典的二维动态规划问题。定义状态dp[i][j]表示把子串s[i..j]变成回文串所需的最少插入次数。转移分为两种情况如果s[i] s[j]两端已经匹配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 最小插入次数的完整实现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]; }注意循环顺序必须按照区间长度从小到大。因为计算长区间需要依赖更短区间的结果如果直接枚举 i、j很可能某个dp[i1][j-1]还没算出来。这是区间 DP 最常见的坑。4.3 把“次数”升级成“方案数”变体还可能要求统计“有多少种不同的最短插入方案”。这需要在 DP 过程中同步维护方案数。定义ways[i][j]表示达到dp[i][j]最小次数的方案数。转移时s[i] s[j]方案数等于内部子串的方案数。s[i] ! s[j]如果dp[i1][j] dp[i][j-1]则方案数继承ways[i1][j]反之继承ways[i][j-1]如果两者相等方案数相加。这里要注意当两端不相等时实际插入位置不同会导致结果不同但计数模型只需关注“选择”的路径。如果题目还要求去重情况会复杂一些通常需要引入字符串哈希或者构造自动机笔试一般不会考到那么深。真遇到的话先写朴素 DP 拿部分分再考虑优化。5. 笔试实战中的高频坑与测试用例清单5.1 边界条件十个必须过的用例我在模拟面试时经常拿下面这组用例检验候选人的实现这里直接分享出来输入头部插入答案说明空串很多人忘记判空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 数组初始化或下标更新出了偏差。5.2 重现的经典翻车现场常见的错误有四种。第一KMP 的 next 数组循环写成for (int i 0; i n; i)而不是从 1 开始。next[0]一定初始化为 0否则首个字符比较逻辑全乱。第二拼接临时串时忘记加分隔符。s aaaa的情况不加分隔符会得到虚假的重叠匹配直接导致输出多出几个字符。分隔符一定要选原串中不存在的字符笔试时通常用#但如果输入本身就含#就要换或$。稳妥做法是再加一个判断或者用 platform 不出现的 char实际竞赛里常用char(0)。第三对字符串长度为奇偶时的回文中心判断错误。在 Manacher 方案里插入#之后所有回文都变奇数长度回文半径减一才是原串长度这一步经常有人多减或少减。第四使用递归方案时递归深度过大导致栈溢出。虽然 O(n²) 超时已经是硬伤但有些考生在自测小数据时又因为递归写法爆栈连部分分都拿不到。如果面试要求写一个“能跑”的版本优先写迭代。5.3 笔试现场的答题策略我个人的建议是按这个顺序分配时间拿到题目后先确认变体类型。如果是头部插入直接默写 KMP 版本。如果是尾部插入把 KMP 版本对称改动。如果是两端插入考虑 Manacher 但不要盲目使用先用最长回文前缀的结论思考一下很多时候两端插入的最优解其实就是“从左边找最长回文前缀补右边”和“从右边找最长回文后缀补左边”二选一不一定真的需要 Manacher。只有任意位置插入才切换到区间 DP。做完基础版本后立刻跑几个边界用例空串、单字符、全同字符、本身就是回文串、完全无重复字符。这五个用例基本能覆盖九成逻辑错误。6. 从这道题延展出的算法思维6.1 回文串题型的统一思考框架回文串问题在笔试中非常高频从最简单的判断回文到最长回文子串、最长回文子序列、最短回文串再到插入次数统计本质都是在回答两个问题回文的“中心”在哪回文的“覆盖范围”有多大。双指针从两边往中间找适合判断型问题。中心扩展适合求最长回文子串但最坏 O(n²)。Manacher 用对称性加速中心扩展是 O(n) 求最长回文子串的标准答案。KMP next 表擅长解决“前缀和后缀匹配”的问题所以它能直接套用到头部或尾部插入。区间 DP 适合“允许内部修改”的构造型问题。面试官如果继续追问“能不能优化到 O(n log n)”你还可以提到二分 字符串哈希枚举回文半径时用哈希快速判断左右两侧是否相等。这个思路在做后缀数组题时也经常用到掌握它相当于多了一把钥匙。6.2 一题多解背后的出题意图“最短回文串的变体”之所以被放在第一题我理解出题人想考察的是候选人有没有形成一套完整的字符串算法工具箱。第一题不会故意为难你但如果你连“变体”和“经典题”的差异都看不出来或者只背了 LeetCode 原题代码、遇到改动就无从下手那基本就被淘汰了。这种题的答题表现往往能直接反映一个人的刷题方式。只会背题解的人写出来的代码结构死板边界变量命名混乱容易在变体类型切换时迷路。真正理解原理的人可以三分钟内把 KMP 版本改造成尾部插入版本。6.3 后续扩展方向如果你还想继续深挖可以试着做这几个练习输出具体的最短回文串而不是长度要求对多种方案去重。将任意位置插入的最小次数问题改成“最少删除几个字符可以变成回文串”等价变换为“最长回文子序列长度”。用二分 字符串哈希重写头部插入版本对比 KMP 版本在常数和可读性上的差异。在区间 DP 版本里加入滚动数组把空间复杂度从 O(n²) 降到 O(n)。我在实际工作中处理日志数据清洗时遇到过“给一串缺失引号的内容自动补全成合法对称结构”的需求底层思路就和这道题完全一致。字符串算法的价值不在炫技而是当数据形状不对时你能快速判断出该用哪种拼接策略。我个人在考场上最深的体会是不要急着写代码先用三分钟把变体类型标在草稿纸上写出状态定义或者匹配关系再动手。代码只是最后一步的翻译工作思路清晰了代码基本不会错。这道题覆盖的 KMP、Manacher、区间 DP 三个核心工具值得你反复练习到下意识就能写出来。下次不管它怎么变只要看到“回文串”“插入字符”“最短”这几个关键词你能第一时间锁定正确的算法族这道题就拿下了。