代码1

第一次自己做出hard题
Runtime: 118 ms, faster than 42.09% of Java online submissions for Shortest Palindrome.

class Solution {
    public String shortestPalindrome(String s) {
        int n = s.length();
        if (n < 2) return s;
        char[] c = s.toCharArray();
        for (int i = n / 2; i >= 0; i--) {
            if (i == n - 1) continue;
            if (valid(c, i, i)) {
                return helper1(c, i);
            } else if (valid(c, i, i - 1)) {
                return helper2(c, i, i - 1);
            }
        }
        return "";
    }
    public boolean valid(char[] c, int i, int k) {
        while (k >= 0 && i < c.length) {
            if (c[k--] != c[i++]) return false;
        }
        return true;
    }
    public String helper1(char[] c, int index) {
        int length = 2 * c.length - 2 * index - 1;
        char[] ch = new char[length];
        for (int i = 0; i < length - c.length; i++) {
            ch[i] = c[c.length - 1 - i];
        }
        for (int i = length - c.length; i < length; i++) {
            ch[i] = c[i - length + c.length];
        }
        return new String(ch);
    }
    public String helper2(char[] c, int index1, int index2) {
        int length = (c.length - index1 - 1) - index2 + c.length;
        char[] ch = new char[length];
        for (int i = 0; i < length - c.length; i++) {
            ch[i] = c[c.length - 1 - i];
        }
        for (int i = length - c.length; i < length; i++) {
            ch[i] = c[i - length + c.length];
        }
        return new String(ch);
    }
}

代码2

kmp
Runtime: 6 ms, faster than 70.85% of Java online submissions for Shortest Palindrome.

class Solution {
    public String shortestPalindrome(String s) {
        String temp = s + "#" + new StringBuffer(s).reverse().toString();
        int[] table = getTable(temp);
        return new StringBuffer(s.substring(table[table.length - 1])).reverse().toString() + s;
    }
    public int[] getTable(String s) {
        int[] table = new int[s.length()];
        int index = 0;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(index)) {
                table[i] = table[i - 1] + 1;
                index++;
            } else {
                index = table[i - 1];
                while (index > 0 && s.charAt(i) != s.charAt(index)) {
                    index = table[index - 1];
                }
                if (s.charAt(i) == s.charAt(index)) index++;
                table[i] = index;
            }
        }
        return table;
    }
}