214 Shortest Palindrome

214. Shortest Palindrome

1. Question

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".

2. Implementation

(1) Brute Force

class Solution {
    public String shortestPalindrome(String s) {
        String revStr = new StringBuilder(s).reverse().toString();
        int n = s.length();

        for (int i = 0; i < n; i++) {
            if (s.substring(0, n - i).equals(revStr.substring(i))) {
                return revStr.substring(0, i) + s;
            }
        }
        return "";
    }
}

(2) KMP Algorithm

思路: 这题的本质是找出从第一位开始算起的最长palindrome substring,我们设为k，输入string的长度为n，然后需要插入的字符数的个数就等于n - k，这样是最短的。而找出从第一位开始算的最长palindrome substring的思路恰好也是我们计算KMP lookup table的本质(找出最长的共同前缀和后缀的长度)一样。关于KMP中求next数组的思想可以参考这篇文章。这里需要注意的一个地方是我们必须在s 和 revStr中间插入一个特殊符号，否则最后的的结果是不正确的。比如,s = "aaaa", s + revStr = “aaaaaaaa” , 那么最长的共同前缀后缀是7，这显然不对，因为超过s的长度。

class Solution {
    public String shortestPalindrome(String s) {
        String revStr = new StringBuilder(s).reverse().toString();
        int[] next = getNextTable(s + "#" + revStr);

        return revStr.substring(0, s.length() - next[next.length - 1]) + s;
    }

    public int[] getNextTable(String s) {
        int[] next = new int[s.length()];
        int len = 0;
        for (int i = 1; i < s.length(); i++) {
            while (len > 0 && s.charAt(i) != s.charAt(len)) {
                len = next[len - 1];
            }

            if (s.charAt(i) == s.charAt(len)) {
                ++len;
            }
            next[i] = len;
        }
        return next;
    }
}

3. Time & Space Complexity

Brute Force: 时间复杂度O(n^2), 空间复杂度O(n)

KMP Algorithm: 时间复杂度O(n), 空间复杂度O(n)