214. Shortest Palindrome

Version #1
Find the longest palindrome prefix
beats 17.77 %
Time O(n^2)
Space O(1)
class Solution {
    private int max;
    public String shortestPalindrome(String s) {
        // To find the longest palindrome prefix
        max = 0;
        for (int i = 0; i < s.length(); i++) {
            shortestPalindrome(s, i, i);
            shortestPalindrome(s, i, i + 1);
        }
        StringBuilder sb = new StringBuilder(s.substring(max, s.length()));
        sb = sb.reverse().append(s);
        return sb.toString();
    }
    private void shortestPalindrome(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        // Is prefix
        if (left == -1) {
            max = Math.max(max, right - left - 1);
        }
    }
}

Version #2