214. Shortest Palindrome

https://leetcode.com/problems/shortest-palindrome/description/

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:

Given "aacecaaa", return "aaacecaaa".

Given "abcd", return "dcbabcd".

Thoughts

在s前插入最少的字符使得s变成回文。如果能找到在s中从0开始能形成的最长子回文段, 再把后面的字符串颠倒贴到s前，此时就是最短的回文。比如catacb中最长是catac, 把b翻转贴到前面, 得到最短的回文bcatacb。为了寻找从0开始的最长回文，把revStr贴到后面并用"#"分割开，得到"catacb#bcatac"，然后找这个新str中prefix和(正着来的)suffix 中最长匹配，得到"catac"，长度为5，把revS中后5个删掉再贴到s前即所求。下面是如何求str中prefix和suffix中最长匹配? 用KMP里的next数组。让next[i]表示以i结尾的字串中的最长匹配prefix/suffix。 比如abacabab对应的next为00101231。用类似dp里的string match思想，j初始成next[i - 1]，即利用上次的结果看当前的i是否和上次结果的下一个匹配，比如看最后abab里的最后一个b和abac的c是否匹配。如果s[i] != s[j]，应把后缀收缩到下一个与前缀相等的长度，这里b != c，把aba收缩到与下一个与前缀相等的长度，对应abacaba里的abacaba，它相当于看aba内部里前后缀匹配长度，也就是1。

c a t a c b # b c a t a c 0 0 0 0 1 0 0 0 1 2 3 4 5

Code

/*
 * @lc app=leetcode id=214 lang=cpp
 *
 * [214] Shortest Palindrome
 */

// @lc code=start
class Solution {
public:
    string shortestPalindrome(string s) {
        const auto next = [](string s) {
            const int N = s.length();
            vector<int> dp(N, 0);
            for (int i = 1; i < N; ++i) {
                int j = dp[i - 1];
                while (j > 0 && s[i] != s[j]) {
                    j = dp[j - 1];
                }
                if (s[i] == s[j]) dp[i] = j + 1;
            }
            return dp;
        };
        auto rev_s = s;
        reverse(rev_s.begin(), rev_s.end());
        const auto next_vec = next(s + "#" + rev_s);
        return rev_s.substr(0, s.size() - next_vec[next_vec.size() - 1]) + s;
    }
};
// @lc code=end

class Solution {
    private int[] kmpTable(String str) {
        int[] f = new int[str.length()];
        // build KMP table
        // i -> suffix boundary
        // j -> prefix boundary
        for (int i = 1; i < str.length(); i++) {
            // update prefix boundary
            int j = f[i - 1]; // j 表示前后缀相同的个数
            // move to the last prefix boundary match
            while (j > 0 && str.charAt(i) != str.charAt(j)) {
                // 如果s[i]和s[j]不相等了, 就倒退
                j = f[j - 1];
            }

            // if prefix boundary matches suffix boundary, increase prefix length
            if (str.charAt(i) == str.charAt(j)) {
                f[i] = j + 1;
            } else {
                f[i] = 0;
            }
        }

        return f;
    }


    public String shortestPalindrome(String s) {
        String revS = new StringBuilder(s).reverse().toString();
        String str = s + "#" + revS;

        int[] f = kmpTable(str);
        return revS.substring(0, s.length() - f[str.length() - 1]) + s;
    }
}

Analysis

时间复杂度O(N).