LeetCode - 解题笔记 - 214 - Shortest Palindrome

Solution 1

观察：任意输入都有平凡解：s[1:]的逆序，因此新增加的前缀必然比s的长度小（最大为s-1）

启发：找到一个s的最短后缀子串s[i:]，其中s[:i]为一个回文串，这样额外增加的前缀就是这个最短子串的逆序，整体长度最短

限制：输入长度限制，枚举切分位置并线性判定回文串为二次复杂度，会超时

方案：寻找更简便的回文串判定方法（常数或对数）

【官方题解】Rabin-Karp算法，基于哈希值（了解：旋转哈希）快速查找query pattern

本题中，我们就是试图使用该算法找到回文串（query就是自己的逆序），需要一个简单的哈希计算方法。官方实现就是选择了一个比较大的base进行十进制转换，并用mod约束（假设碰撞概率极低），这样可以基于历史结果快速计算新前缀的哈希。

• 时间复杂度：$O(N)$，其中$N$为输入字符串长度，哈希部分常数计算复杂度，整体为线性
• 空间复杂度：$O(1)$，仅维护常数个状态量

class Solution {
public:
    string shortestPalindrome(string s) {
        int n = s.size();
        if (n <= 1) { return s; }
        
        // 至少大于字符集大小的base和至少为其平方的mod，显著降低碰撞概率
        int base = 131, mod = 1e9+7;
        
        int left = 0, right = 0, exp = 1;
        int best = -1;
        
        for (int i = 0; i < n; ++i) {
            left = ((long long)left * base + s[i]) % mod;
            right = (right + (long long)exp * s[i]) % mod;
            
            if (left == right) { best = i;}
            
            exp = (long long)exp * base % mod;
        }
        
        string suffix = (best == n - 1 ? "" : s.substr(best + 1, n));
        reverse(suffix.begin(), suffix.end());
        string ans = suffix + s;
        
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

Solution 2

【官方题解】KMP算法，暂时跳过不学习，等需要的时候再学习

Solution 3

Solution 1的Python实现

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        n = len(s)
        if n <= 1: return s
        
        base, mod = 131, 10**9 + 7
        
        left, right, exp = 0, 0, 1
        best = None
        
        for i in range(n):
            left = (left * base + ord(s[i])) % mod
            right = (right + exp * ord(s[i])) % mod
            
            if left == right: best = i
                
            exp = exp * base % mod
        
        suffix = "" if best == n - 1 else s[best + 1:]
        ans = suffix[::-1] + s
        
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22