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

Example 1:

Input: "aacecaaa"
Output: "aaacecaaa"

Example 2:

Input: "abcd"
Output: "dcbabcd"

Analysis:
最佳答案是KMP算法，在面试中不可能做得出来。
"abcd" reverse it to dcab, check whether reversed string's substring at the index 0 of s. If yes, the shortest palindrome is r.substring(0, i) + s.
i  = 0
sub:dcab
i = 1
sub: cab
i = 2
sub: ab (qualify res = dc + ab + cd)
Solution:

class Solution {
    public String shortestPalindrome(String s) {
        if (s == null || s.length() == 0)
            return "";
        StringBuilder sb = new StringBuilder(s);
        String r = sb.reverse().toString();
        for (int i = 0; i < r.length(); i++) {
            if (s.startsWith(r.substring(i))) {
                return r.substring(0, i) + s;
            }
        }
        return "";
    }
}