214. 最短回文串

Leetcode题解

解题思路

枚举回文中心：

1.当前位置为回文中心，那么从「该位置之前到字符串首部这段字符串」和「该位置之后截取与前一部分相同长度的字符并反转」如果两部分相等，那么可以往首部按顺序添加剩余的字符即可构成回文串。

2.以当前位置和前一个位置为回文中心（前提是两字符相等），判断方法同1。

依次枚举，记录最小的长度和回文中心的类型和位置即可。

可以用字符串哈希在$O(1)$时间内判断两字符串是否相等，核心公式，已知字符串S+T的哈希值为$H(S+T)$和字符串S的哈希值为$H(S)$的哈希值，那么字符串T的哈希值为$H(T)=H(S+T)-H(S)*base^{len(T)}$

,,,,,,

时间复杂度：$O(n)$

空间复杂度：$O(n)$

代码

class Solution {
    public String shortestPalindrome(String s) {
        if (s.length() <= 1) return s;
        StringBuilder sb = new StringBuilder(s).reverse();
        int n = s.length();
        long[] hash = new long[n + 1]; // 源字符串哈希
        long[] hashR = new long[n + 1]; // 反转后字符串哈希
        long[] p = new long[n + 1]; // 保存base的i次方，减少运算
        int base = 131;
        p[0] = 1; // base的零次方为1
        // 计算哈希值
        for (int i = 1; i <= n; i++) {
            hash[i] = hash[i - 1] * base + s.charAt(i - 1) - 'a' + 1;
            hashR[i] = hashR[i - 1] * base + sb.charAt(i - 1) - 'a' + 1;
            p[i] = p[i - 1] * base;
        }
        // f：标记最短回文串的回文中心为单个还是两个
        // min：最短回文串的长度，初始时以第一个字母为回文中心必定能添加字幕构成回文串，长度为2*s.length() - 1
        // idx：回文中心的下标，初始为第一个字母的下标
        int f = 1, min = s.length() * 2 - 1, idx = 0;
        // 回文中心最多只能到 n/2，否则无法通过在字符串前面添加字符来构成回文串
        for (int i = 1; i <= n / 2; i++) {
            // 以 i 为回文中心能添加字母构成回文串
            if (n - 2 * i - 1 >= 0 && hash[i] == hashR[n - i - 1] - hashR[n - i - 1 - i] * p[i]) {
                // 更新最短长度
                if (n - i + n - (i + 1) < min) {
                    min = n - i + n - (i + 1);
                    f = 1;
                    idx = i;
                }
            } 
            
            if (s.charAt(i) == s.charAt(i - 1)) {
                // 以 i 和 i+1 为回文中心能构成回文串
                if (hash[i - 1] == hashR[n - i - 1] - hashR[n - i - 1 - (i - 1)] * p[i - 1]) {
                    // 更新最短长度
                    if (n - i - 1 + n - i + 1 < min) {
                        min = n - i + n - i;
                        f = 2;
                        idx = i;
                    }
                }

            }
        }
        // 根据回文中心的类型，返回相应的最短回文串
        if (f == 1) return new StringBuilder(s.substring(idx + 1)).reverse().toString() + s.substring(idx);
        return new StringBuilder(s.substring(idx + 1)).reverse().toString() + s.substring(idx - 1);
    }
}