LeetCode 214. 最短回文串

约 5 分钟
文章信息 7 个分类 4 个标签
分类
LeetCode CodeTop 困难 未解决 5-10 腾讯 字节
标签
字符串 哈希函数 字符串匹配 滚动哈希

题目描述

✅ 214. 最短回文串

image-20260928235024484

题意分析

只能在原字符串的前面添加字符，使最终结果成为回文串，并返回长度最短的结果。原串内部和末尾都不能插入字符，也不能删除或调整原字符顺序。

因为只能往前补，需要保留的是从原串开头开始的一段回文，而不是任意位置的最长回文子串。原串已经是回文或为空时，不需要添加字符。

解法：KMP 求最长回文前缀

核心思路

[!blue]

将原串写成 P + T，其中 P 是回文前缀，那么在前面补上 reverse(T)，得到 reverse(T) + P + T，一定是回文。前缀 P 越长，未覆盖后缀 T 越短，需要补的字符越少。

反过来，若在前面补 m 个字符，回文对称性要求它们与原串最后的 m 个字符对应；中间剩下的原前缀必须自身回文。因此寻找最少添加量，就等价于寻找最长回文前缀。最优方案无需添加超过原串长度的字符，因为把整个原串反转后补在前面已经可行。

令 reversed = reverse(s)。它末尾的 L 个字符，正是原串前 L 个字符的反转。所以“原串长度为 L 的前缀是回文”等价于“原串前 L 个字符与反转串后 L 个字符相同”。

构造 combined = s + "#" + reversed，对它求 KMP 前缀函数。lps[i] 表示截至位置 i 的前缀中，最长相等真前缀和真后缀的长度；真前缀不能包含整段本身。分隔符不属于输入字母且只出现一次，所以完整拼接串的合法相等前后缀不能跨过分隔符，长度不超过原串长度。最后一项于是恰好对应原串的最长回文前缀。

构造前缀函数时，当前字符若无法延长已有匹配，就沿 lps[length - 1] 尝试更短的相等前后缀；它们是仍可能接上当前字符的候选，不能直接全部清零。得到最终长度 L 后，取反转串前 n - L 个字符补到原串前面即可。

解题步骤

  1. 将原串反转，得到 reversed，再用不属于输入字符集的 # 连接两串。
  2. 为拼接串创建前缀函数数组，从第二个字符开始扫描。
  3. 当前字符失配时，反复令 length = lps[length - 1]；能够匹配时再增加长度，写入 lps[i]。
  4. 取 lps 最后一项作为最长回文前缀长度 L。
  5. 返回 reversed 开头的 n - L 个字符加上原串。空串时拼接结果只有分隔符，L 为零，结果仍为空。

代码实现

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)$。反转、拼接和生成结果均为线性；计算前缀函数时，匹配长度每次增加最多一，全部回退总量不超过此前增加量，因此也是线性。
  • 空间复杂度：$O(n)$，保存反转串、拼接串和前缀函数数组，最终答案长度也不超过线性规模。

关键点总结

[!green]

  • 最少前补字符等价于最大化原串中无需外部配对的回文前缀。
  • 原前缀的反转出现在反转串末尾，可以转成相等前后缀问题。
  • 唯一分隔符阻止跨段匹配，最后一项才描述完整拼接串的边界。
  • 未保留后缀的反转位于 reversed 开头，按 n - L 截取。

易错点总结

[!yellow]

  • 找原串内部任意位置的最长回文段，不能保证只在最前面添加字符就能完成对称。
  • 拼接时省略分隔符，可能产生跨过原串边界的匹配，长度不再代表合法回文前缀。
  • 分隔符属于输入字符集，无法保证只出现一次，破坏隔离依据。
  • 取整个 lps 的最大值，而不是最后一项，内部位置的最长边界未必对应完整原串的回文前缀。
  • 失配时直接清零，丢掉仍可能继续延长的较短相等前后缀。
  • 从反转串尾部取需要补的部分，取到的是原前缀的反转，而非尚未配对的后缀。

相似题目

题目 难度 关联与区别
5. 最长回文子串 中等 本题只能在前面补字符，所以关键是最长回文前缀；原题寻找任意位置的最长回文子串。
459. 重复的子字符串 简单 同样可以利用KMP前缀函数提取边界信息，本题比较原串与逆序串，原题据此判断周期。
28. 找出字符串中第一个匹配项的下标 简单 通过字符与模式前缀的匹配状态避免重复比较；本题将回文前缀转为正反串匹配，该题寻找第一个完整匹配的位置。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/66613602
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！