Solutions CS101

Appearance

T214.最短回文串 ​

string, hash, rolling hash, https://leetcode.cn/problems/shortest-palindrome/

给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

示例 1：

输入：s = "aacecaaa"
输出："aaacecaaa"

示例 2：

输入：s = "abcd"
输出："dcbabcd"

提示：

  • 0 <= s.length <= 5 * 10^4
  • s 仅由小写英文字母组成

问题本质

题目要求：

给一个字符串 s，在前面添加最少字符使其成为回文。

等价于：

找出 s 的 最长前缀回文，然后把剩余的后缀反转加到前面即可。

用 KMP 可以非常优雅地求出最长前缀回文，从而得到最短回文串。这个方法 完全 O(n)

KMP 版本思路 ​

  1. 构造 s + '#' + s[::-1]
    • 用 # 分隔，避免交叉匹配
  2. 计算 KMP 前缀函数（next 数组 / lps）
    • lps[-1] 就是 s 的最长前缀回文长度
  3. 将后缀（不是回文的部分）反转加到前面
python
class Solution:
    def shortestPalindrome(self, s: str) -> str:
        if not s:
            return s

        # 构造新串
        t = s + '#' + s[::-1]
        n = len(t)
        lps = [0] * n  # KMP 前缀函数

        for i in range(1, n):
            j = lps[i - 1]
            while j > 0 and t[i] != t[j]:
                j = lps[j - 1]
            if t[i] == t[j]:
                j += 1
            lps[i] = j

        # lps[-1] = 最长前缀回文长度
        pre_len = lps[-1]
        suffix = s[pre_len:]  # 非回文后缀
        return suffix[::-1] + s

🔍 示例

python
s = "aacecaaa"
# 构造 t = "aacecaaa#aaacecaa"
# lps[-1] = 7
# 非回文后缀 = s[7:] = "a"
# 结果 = "a" + s = "aaacecaaa"
s = "abcd"
# t = "abcd#dcba"
# lps[-1] = 1
# 非回文后缀 = s[1:] = "bcd"
# 结果 = "dcb" + s = "dcbabcd"

✅ 特点

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)
  • 结构简洁、无需哈希
  • 与你之前 DP 的思想类似：按“right 扩展”寻找最长前缀回文

rolling hash（双哈希） ​

使用 滚动哈希模拟 O(1) 判断子串是否为回文，保持“按 right 扩展”的思路，是 O(n)。

✅ 思路（仍然是找从 0 位置开始的最长回文）

如果 s 的前缀 s[0..k] 是回文，那么答案是：

reverse(s[k+1:]) + s

所以我们要找：

最长前缀回文

用滚动哈希（forward / backward）来做，就像是在 O(1) 查询 s[l..r] 是否回文。

✅ Python：双哈希 + 最长前缀回文（O(n)）

python
class Solution:
    def shortestPalindrome(self, s: str) -> str:
        n = len(s)
        if n <= 1:
            return s

        base = 131
        mod1 = 10**9 + 7
        mod2 = 10**9 + 9

        # 预处理幂
        pow1 = [1] * (n + 1)
        pow2 = [1] * (n + 1)
        for i in range(1, n + 1):
            pow1[i] = pow1[i - 1] * base % mod1
            pow2[i] = pow2[i - 1] * base % mod2

        # 前向哈希
        h1 = [0] * (n + 1)
        h2 = [0] * (n + 1)

        # 反向哈希（相当于 reversed(s) 的前缀哈希）
        rh1 = [0] * (n + 1)
        rh2 = [0] * (n + 1)

        for i, ch in enumerate(s):
            v = ord(ch) - ord('a') + 1
            h1[i + 1] = (h1[i] * base + v) % mod1
            h2[i + 1] = (h2[i] * base + v) % mod2

        rs = s[::-1]
        for i, ch in enumerate(rs):
            v = ord(ch) - ord('a') + 1
            rh1[i + 1] = (rh1[i] * base + v) % mod1
            rh2[i + 1] = (rh2[i] * base + v) % mod2

        # 工具函数：取哈希
        def get_hash(h, L, R, mod, pow):
            """ 返回 s[L..R] 的哈希 """
            return (h[R + 1] - h[L] * pow[R - L + 1]) % mod

        # ---------- 类似“按 right 扩展”找最长前缀回文 ----------
        max_pre = 0
        for right in range(n):
            # s[0..right] 是否回文？
            # 对应 reversed(s) 的区间为：
            #    s[0..right] 反向后映射到 rs[n-1-right .. n-1]
            L = n - 1 - right
            R = n - 1

            # 双哈希判定
            if (get_hash(h1, 0, right, mod1, pow1) == get_hash(rh1, L, R, mod1, pow1) and
                get_hash(h2, 0, right, mod2, pow2) == get_hash(rh2, L, R, mod2, pow2)):
                max_pre = right

        # 后半段不是回文 → 反转并加到前面
        suffix = s[max_pre + 1:]
        return suffix[::-1] + s

若你想，我还能给：

  • KMP 版本（更短的 O(n) 写法）
  • 只用 单哈希但降低冲突的技巧
  • 一个 打印每次 right 扩展判断过程 的可视化代码
  • 用 Manacher 求前缀回文版本（更炫技）