Shortest Palindrome

题目地址：
https://leetcode.com/problems/shortest-palindrome/#/description

题目：

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

解题思路：
这道题应该用recursion加双指针的解法，left和right之间的部分是可以call 自己来用recursion解决的。这里要注意的是只能够在前面加来构成palindrome，所以right指针是一直要往左移动的。

代码：

public String shortestPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    for(; right >= 0; right--){
        if(s.charAt(left) == s.charAt(right)){
            left++;
        }
    }
    if(left == s.length()){
        return s;
    }
    String prefix = s.substring(left);
    return new StringBuilder(prefix).reverse().toString() + shortestPalindrome(s.substring(0, left)) + prefix;
}

这里有另外一种方法，We can solve this problem by using one of the methods which is used to solve the longest palindrome substring problem. Specifically, we can start from the center and scan two sides. If read the left boundary, then the shortest palindrome is identified. reference: http://www.programcreek.com/2014/06/leetcode-shortest-palindrome-java/

public String shortestPalindrome(String s) {
    if (s == null || s.length() <= 1)
        return s;

    String result = null;

    int len = s.length();
    int mid = len / 2;
    
    // starts from mid is smart
    for (int i = mid; i >= 1; i--) {
        if (s.charAt(i) == s.charAt(i - 1)) {
            if ((result = scanFromCenter(s, i - 1, i)) != null)
                return result;
        } else {
            if ((result = scanFromCenter(s, i - 1, i - 1)) != null)
                return result;
        }
    }

    return result;
}

private String scanFromCenter(String s, int l, int r) {
    int i = 1;

    //scan from center to both sides    for (; l - i >= 0; i++) {
        if (s.charAt(l - i) != s.charAt(r + i))
            break;
    }

    //if not end at the beginning of s, return null     if (l - i >= 0)
        return null;

    StringBuilder sb = new StringBuilder(s.substring(r + i));
    sb.reverse();

    return sb.append(s).toString();
}