🌕🌕🌕🌗 214. 最短回文串

难度: 🌕🌕🌕🌗

问题描述

---

解法

class Solution {
    public String shortestPalindrome(String s) {
        // 思路：
        // 假设 s == acecada
        // 如果爆搜，首先判断 s 是否为回文串
        //      若是，直接返回
        //      若不是，去掉最后一个字符，判断剩下的是否是回文串，若不是，继续去除，直到为回文串
        //      将去掉的字符逆序添加到 s 前面即可
        //      例中，aceca 为回文串，去掉的字符是 da
        //      返回结果为 ad acceca da
        // 每次去掉一个字符后，都需要重新判断剩下的字符串是否为回文串，复杂度高，采用 KMP 
        // 将 s & s 的逆序拼接在一起，
        // 如 acecada # adaceca
        // 获取 next[] 为  [0000101 0 1012345]
        // 由于 s # s' 肯定是回文串，因此 next[len - 1] >= 0 只需要查看 next[len - 1] 即可确定拼接字符串的最长回文串长度
        // 例中，next[len - 1] == 5 说明 s 的前 5 个字符已经是回文串，只需要添加 [5, len - 1] 的字符串的倒序即可
        String rev = new StringBuilder(s).reverse().toString(); // 获取 s 的倒序字符串
        String cur = s + '#' + rev; // 添加 ‘#’ 后可保证 next[len - 1] 必 < len
        // 因为，由于 '#' 肯定匹配不到字符与之相等，匹配指针肯定会回到 下标0，之后即使一直匹配，也会是最大值 len - 1
        int total = cur.length();
        // 获取 next[] 数组
        int[] next = getNext(cur, total);
        int cut = next[total - 1]; // s 的 [cut, len - 1] 子串需要切割反转拼接在最前面
        int len = s.length();
        if(cut == len) {
            return s; // 说明自身就是回文串
        }
        return new StringBuilder(s.substring(cut, len)).reverse().append(s).toString();
    }

    private int[] getNext(String str, int len) {
        int[] next = new int[len];
        next[0] = 0; // 虽然默认 == 0，但还是显式写出来
        int left = 0; // 左指针，表示当前应该和 right 指针的值进行匹配，前面的部分已经匹配成功；若当前不匹配，会回退
        for(int right = 1; right < len; right ++) {
            // right 为右端点
            while(left > 0 && str.charAt(left) != str.charAt(right)) {
                // 说明 [left] & [right] 不匹配，left 回退到满足条件的回退节点处
                // 也就是说，[0, left] 与 [?, right] 不匹配，那么回退到上一节点，直到一直没有匹配成功
                left = next[left - 1]; 
            }
            // 到这里，说明 [left] == [right] 或 left == 0
            // 若 [left] == [right] 那么 left 指针需要后移一位，若是 left == 0 仍然不匹配，那么 left 不移动
            if(str.charAt(left) == str.charAt(right)) {
                left ++; // 只有一次挽救机会，因此 用 if
            }
            next[right] = left;
        }
        return next;
    }
}

---

输出