[LeetCode] Shortest Palindrome

Problem:

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

Thinking:

Find out the length of longest prefix palindrome of S.
Then, the shortest palindrome would be:
reverse(s.substring(length, s.length())) + s.

Java Code:

Version 1: Time Limit Exceeded

    public String shortestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        
        //find the longest prefix
        int prefix_l = 1;
        for (int i = 1; i < s.length(); i++) {
            if (isPalindrome(s, 0, i)) {
                prefix_l = i + 1;
            }
        }
        return new String(new StringBuffer(s.substring(prefix_l, s.length())).reverse().toString() + s);
    }
    
    private boolean isPalindrome(String s, int start, int end) {
        while (start < end) {
            if (s.charAt(start) == s.charAt(end)) {
                start++;
                end--;
            } else {
                return false;
            }
        }
        return true;
    }

Version 2 (Version 1 optimized): Accepted
Optimization of the process of finding the longest prefix palindrome.
for each index i (i < s.length()/2), generate the smallest start and largest end which could make s.substring(start, end) a palindrome. If start == 0, then it is a prefix palindrome.

reference: https://leetcode.com/discuss/36807/c-8-ms-kmp-based-o-n-time-%26-o-n-memory-solution

    public String shortestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        
        //find the longest prefix
        int prefix_l = 1;
        for (int i = 0; i < s.length(); ) {
            int start = i;
            int end = i;
            while (end < s.length() - 1 
                   && s.charAt(end) == s.charAt(end + 1)) {
                end++;
            }
            i = end + 1;
            while (start > 0 && end < s.length() - 1 
                   && s.charAt(start - 1) == s.charAt(end + 1)) {
                start--;
                end++;
            }
            if (start == 0 && end - start + 1 > prefix_l) {
                prefix_l = end -start + 1;
            }
        }
        
        //construct shortest palindrome
        return new String(new StringBuffer(s.substring(prefix_l, s.length())).reverse().toString() + s);
    }