214. Shortest Palindrome

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

Analysis

Scan the string from the end to start to find the longest palindrome; Add the chars after the end idx to the front of the string.

My Solution

public String shortestPalindrome(String s) {
    char[] input = s.toCharArray();
    int n = input.length - 1;
    StringBuilder sb = new StringBuilder();
    while (n > 0) {
        if (isPal(0, n, input)) {
            break;
        } else {
            sb.append(input[n]);
            n--;
        }
    }
    return sb.toString() + s;
}
private boolean isPal (int left, int right, char[] input) {
    while (left < right) {
        if (input[left] != input[right]) {
            return false;
        }
        left++; right--;
    }
    return true;
}

Other Solution and KMP Algorithm

solution: https://leetcode.com/problems/shortest-palindrome/discuss/60216/

kmp: http://www.ruanyifeng.com/blog/2013/05/Knuth–Morris–Pratt_algorithm.html