破防！刚办完离职，就收到领导信息，说我的期权被清零。工资也被打了欠条。。。

你有没有刷 LeetCode 的时候，遇到过这么一种题：

给你一个字符串 s，你要在开头加一些字符，让整个字符串变成一个回文串，但加的字符尽可能少。

这题就叫「最短回文串」，英文名是 Shortest Palindrome。初一看，啊？在前面加字符？你不让我在末尾加，你非得我头上插花？这啥操作……

但刷多了你就知道，这种看似莫名其妙的要求，往往藏着挺精巧的思路。

怎么理解这题？

先看个例子：s = "aacecaaa"

我们如果直接把它变成回文，最短的办法就是——在最前面加上 "aa"，变成 "aaacecaaa"，是不是回文了？

但问题来了，你怎么知道加 "aa" 是最短的？你不能暴力一个个试吧？可以，能过样例，时间超一堆。

所以重点来了，这题其实不是看你怎么加，而是找原字符串的哪个前缀是回文，然后剩下的部分反转后加到前面。

举个再明显点的例子：
s = "abcd"
最长的前缀回文是 "a"，那剩下的部分 "bcd" 反转一下 "dcb" 加到前面，结果就是："dcbabcd"

OK，接下来就要搞明白一个问题：怎么高效找“最长的前缀回文”？

这时候，有两个路子：

暴力法

最直觉的思路：从整个字符串开始，逐渐缩短，找出最长的前缀是回文的。

public String shortestPalindrome(String s) {
intn= s.length();
for (inti= n; i >= 0; i--) {
if (isPalindrome(s, 0, i - 1)) {
Stringsuffix= s.substring(i);
StringBuildersb=newStringBuilder(suffix);
return sb.reverse().toString() + s;
        }
    }
return"";
}

privatebooleanisPalindrome(String s, int left, int right) {
while (left < right) {
if (s.charAt(left) != s.charAt(right)) returnfalse;
        left++;
        right--;
    }
returntrue;
}

这个方法很暴力，时间复杂度是 O(n^2)，在小数据量上还行，但碰上上千长度的字符串，那是真的扛不住。

KMP 解法（经典压轴）

这个题的最优解法，用的是 KMP（对，就是那个用来模式匹配的 KMP）。

你可能会问，KMP不是找匹配的吗，和回文有啥关系？

逻辑如下：

1. 1. 你把原字符串 s 拼接成：s + "#" + reverse(s)
2. 2. 然后对这个字符串做 KMP 的 next 数组（也叫 lps）
3. 3. 最后 lps 数组的最后一个值，就是原字符串中最长的前缀回文子串的长度

代码怎么写？来！

public String shortestPalindrome(String s) {
Stringreverse=newStringBuilder(s).reverse().toString();
Stringcombined= s + "#" + reverse;
int[] lps = newint[combined.length()];

for (inti=1; i < combined.length(); i++) {
intlen= lps[i - 1];
while (len > 0 && combined.charAt(i) != combined.charAt(len)) {
            len = lps[len - 1];
        }
if (combined.charAt(i) == combined.charAt(len)) {
            len++;
        }
        lps[i] = len;
    }

Stringadd= reverse.substring(0, s.length() - lps[combined.length() - 1]);
return add + s;
}

这个版本时间复杂度是 O(n)，直接秒杀暴力。再大的字符串也能妥妥拿下，不愧是 KMP，永远的刷题压箱底宝藏算法🏆。

顺便插个嘴

其实每次刷题刷到这种“你得在字符串开头加点什么”，我脑子里总会想起上学那会儿抄作业——人家写完了，我只想在前面补两句让它“看起来是我写的”，改得少又能混过去，这就是最短回文的思路嘛😂。

要注意什么坑？

1. 1. 有些字符串本身就是回文，比如 "aaaa"，你啥都不用加，别多手。
2. 2. 长度为 1 的时候也是回文，别因为边界条件搞错。
3. 3. KMP 实在记不住？就当今天再复习一遍吧，下次刷到还能用。

这题虽然表面是字符串处理，但底子是算法功夫，尤其考察你对字符串匹配的理解。

刷多了题，有时候真觉得这些题像人际关系：你得不断回头看看哪段过去是最值得保留的，然后在当下加点什么，才能让它完整。

啊这，刷题哲学又上线了，行吧，不扯了，该你上场练练了。