What is the main strategy for solving the Shortest Palindrome problem?

The main strategy involves using rolling hashes and string matching algorithms like KMP to identify the longest palindromic prefix and efficiently prepend characters to form the shortest palindrome.

How can I optimize the solution for the Shortest Palindrome problem?

You can optimize the solution by using a rolling hash combined with KMP for efficient string matching, which ensures an O(n) time complexity.

What are the time and space complexities of the solution?

The time complexity is O(n), and the space complexity is O(n), where n is the length of the string.

Can the Shortest Palindrome problem be solved with brute force?

While brute force is possible, it leads to a time complexity of O(n^2), which is inefficient. An optimal solution using rolling hash and KMP is much faster.

What happens if the input string is already a palindrome?

If the string is already a palindrome, no characters need to be added, and the original string will be returned as the shortest palindrome.

#214

Hard

auto_awesomestring·结合·rolling·哈希

LeetCode 题解工作台

最短回文串

给定一个字符串 s ，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。示例 1：输入： s = "aacecaaa" 输出： "aaacecaaa" 示例 2：输入： s = "abcd" 输出： "dcbabcd" 提示： 0 4 s 仅由小写英…

字符串滚动哈希字符串匹配哈希函数

题目描述

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

示例 1：

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

示例 2：

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

提示：

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

lightbulb

解题思路

方法一：字符串哈希

字符串哈希是把一个任意长度的字符串映射成一个非负整数，并且其冲突的概率几乎为 0。字符串哈希用于计算字符串哈希值，快速判断两个字符串是否相等。

取一固定值 BASE，把字符串看作是 BASE 进制数，并分配一个大于 0 的数值，代表每种字符。一般来说，我们分配的数值都远小于 BASE。例如，对于小写字母构成的字符串，可以令 a=1, b=2, ..., z=26。取一固定值 MOD，求出该 BASE 进制对 M 的余数，作为该字符串的 hash 值。

一般来说，取 BASE=131 或者 BASE=13331，此时 hash 值产生的冲突概率极低。只要两个字符串 hash 值相同，我们就认为两个字符串是相等的。通常 MOD 取 2^64，C++ 里，可以直接使用 unsigned long long 类型存储这个 hash 值，在计算时不处理算术溢出问题，产生溢出时相当于自动对 2^64 取模，这样可以避免低效取模运算。

除了在极特殊构造的数据上，上述 hash 算法很难产生冲突，一般情况下上述 hash 算法完全可以出现在题目的标准答案中。我们还可以多取一些恰当的 BASE 和 MOD 的值（例如大质数），多进行几组 hash 运算，当结果都相同时才认为原字符串相等，就更加难以构造出使这个 hash 产生错误的数据。

对于本题，问题等价于找到字符串 s 的最长回文前缀。

记 s 的长度为 n，其最长回文前缀的长度为 m，将 s 的后 n-m 个字符反序并添加到 s 的前面即可构成最短回文串。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        base = 131
        mod = 10**9 + 7
        n = len(s)
        prefix = suffix = 0
        mul = 1
        idx = 0
        for i, c in enumerate(s):
            prefix = (prefix * base + (ord(c) - ord('a') + 1)) % mod
            suffix = (suffix + (ord(c) - ord('a') + 1) * mul) % mod
            mul = (mul * base) % mod
            if prefix == suffix:
                idx = i + 1
        return s if idx == n else s[idx:][::-1] + s

speed

复杂度分析

指标	值
时间	O(n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Understanding of rolling hash and string matching techniques.
question_mark
Ability to implement optimal algorithms for palindrome construction.
question_mark
Knowledge of the KMP algorithm and its application to string problems.

warning

常见陷阱

外企场景

error
Overcomplicating the solution by brute-forcing palindrome checks for each substring.
error
Failing to optimize the solution, leading to an O(n^2) time complexity due to repeated comparisons.
error
Not handling edge cases like an empty string or already palindromic strings efficiently.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Shortest palindrome with case-sensitive characters.
arrow_right_alt
Transforming the string to a palindrome by adding characters at both ends.
arrow_right_alt
Finding the shortest palindrome by appending characters at the end instead of the front.

help

常见问题

外企场景

继续练习

#187 重复的DNA序列 #1392 最长快乐前缀 #1044 最长重复子串