LeetCode 214. 最短回文串

2025-03-13 HGNULB 约 5 分钟

文章信息 7 个分类 7 个标签

分类

题目描述

✅ 214. 最短回文串

题意分析

给定字符串 s，只允许在它的最前面追加若干字符，要求得到的整串是回文，且总长度最短。

「只能加在前面」这个限制极强，它直接决定了答案的形状。设最终答案为 t + s，若 t 的长度为 $m$，那么答案总长为 $m + \lvert s\rvert$，回文性要求答案的后 $m$ 个字符必须是 t 的反转。而答案的后 $m$ 个字符正是 s 的后 $m$ 个字符，于是 t 只能是 s 后缀的反转——t 里不可能出现 s 之外的新字符。进一步，去掉首尾对应的 $m$ 对字符后，中间剩下的正是 s 的前 $\lvert s\rvert - m$ 个字符，它必须自身是回文。

所以问题被完全等价地改写成：求 s 的最长回文前缀。它越长，需要补到前面的后缀就越短，答案也就越短。这是个从「构造最短串」到「求最长某某」的转化，而后者是纯粹的字符串匹配问题。

边界情形：s 为空串或单字符时它本身就是回文，直接返回；s 整体已是回文时不需要补任何字符；s 完全没有长度超过 1 的回文前缀时（如 "abcd"），最长回文前缀退化成首字符，需要补上除首字符外全部内容的反转。字符串长度可以到十万级，这意味着 $O(n^2)$ 的逐个前缀验证会超时，必须做到线性。

解法：KMP 求最长回文前缀

核心思路

只能在字符串前面添加字符，因此最终保留下来的原串前缀必须是回文。设最长回文前缀长度为 $L$，那么只需把后缀 s[L:] 反转后补到前面；$L$ 越大，补的字符越少。所以原问题等价于：

求 s 的最长回文前缀。

令 rev 为 s 的反转。长度为 $L$ 的前缀是回文，当且仅当它等于 rev 的长度为 $L$ 的后缀。构造 combined = s + "#" + rev，对它计算 KMP 前缀函数；最后一个前缀函数值就是最长回文前缀长度。

分隔符 # 必须不出现在原串字符集中，它阻止匹配跨过两段边界。题目限定为小写英文字母，因此可以安全使用 #。

正确性可以从两边说明：任何回文前缀都会形成 combined 的相等前后缀；反过来，分隔符保证相等前后缀分别落在 s 和 rev 中，对应的 s 前缀等于自身反转，因此必为回文。取最长匹配便得到最少补充字符。

解题步骤

反转 s 得到 rev。

拼接 combined = s + "#" + rev。

计算 combined 的前缀函数 lps：失配时沿 lps[length - 1] 回退，匹配时将长度加一。

令 L = lps[combined.length - 1]。

取 rev 的前 $\lvert s\rvert-L$ 个字符拼到 s 前面。

例如 s = "aacecaaa"，最长回文前缀是 "aacecaa"，长度 7；后缀只有 "a"，反转后仍是 "a"，答案为 "aaacecaaa"。若 s = "abcd"，最长回文前缀只有 "a"，需要补 "dcb"。

代码实现

class Solution {
    public String shortestPalindrome(String s) {
        String reversed = new StringBuilder(s).reverse().toString();
        String combined = s + "#" + reversed;
        int[] lps = new int[combined.length()];

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

        int prefixLength = lps[combined.length() - 1];
        return reversed.substring(0, s.length() - prefixLength) + s;
    }
}

func shortestPalindrome(s string) string {
    reversed := reverseBytes(s)
    combined := s + "#" + reversed
    lps := make([]int, len(combined))

    for i, length := 1, 0; i < len(combined); i++ {
        for length > 0 && combined[i] != combined[length] {
            length = lps[length-1]
        }
        if combined[i] == combined[length] {
            length++
        }
        lps[i] = length
    }

    prefixLength := lps[len(combined)-1]
    return reversed[:len(s)-prefixLength] + s
}

func reverseBytes(s string) string {
    chars := []byte(s)
    for left, right := 0, len(chars)-1; left < right; left, right = left+1, right-1 {
        chars[left], chars[right] = chars[right], chars[left]
    }
    return string(chars)
}

复杂度分析

时间复杂度：$O(n)$。反转、构造前缀函数和生成答案都只线性处理字符串；KMP 的回退总次数也是线性的。

空间复杂度：$O(n)$，用于反转串、拼接串和前缀函数数组。

关键点总结

“最少补多少”先转化为“最多保留多少”，即寻找最长回文前缀。

回文前缀等价于 s 的前缀和 reverse(s) 的后缀相等。

KMP 最后一项求的是整个拼接串的最长相等前后缀，不是 lps 数组中的最大值。

分隔符负责隔离两段；若输入字符集不受限，应选择不会冲突的哨兵或改用整型序列。

易错点总结

求成最长回文子串：本题要求回文段必须从下标 0 开始。

拼接时省略分隔符：匹配可能跨越边界，得到超过原串范围的结果。

取 max(lps) 而不是最后一项：内部重复前缀不代表最长回文前缀。

KMP 失配时直接清零：会丢掉可复用匹配并退化到较差复杂度。

从 rev 尾部截取：应补原后缀的反转，它位于 rev 的开头。

相似题目

题目	难度	考察点
28. 找出字符串中第一个匹配项的下标	简单	前缀函数的原始用途，纯粹的模式匹配
459. 重复的子字符串	简单	用末位前缀函数值推断整串的最小循环节
5. 最长回文子串	中等	回文段可以出现在任意位置，不锁定左端点
647. 回文子串	中等	统计所有回文段的数量而非求某个最长的
125. 验证回文串	简单	只做回文判定，考察双指针与字符过滤