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

[balabala]    以当前字符或者当前相邻两个字符为中心向两边扩展，如果左边能一直扩展到边界，则将右边剩余子串翻转后拼接在原字符串前面即构成一个回文。实现中两个要点：
1）中心字符串从原字符串的中间位置向左遍历，组成的首个回文即是最短回文。 因为回文中心越靠近中间则前面额外添加的字符数越少。
2）先判断以当前两字符为中心能否构成回文再判断以当前一个字符为中心的情况。这同样是为了得到最短回文，考虑aaaa, aab 就很容易理解。

这题自己做了两天，因为一开始没有注意到题目中的限定条件，在字符串前面添加额外字符来得到最短回文串。我忽略了这个限定还在想leetcode给的test case也会不周到啊，ba对应的最短回文可以是aba，也可以还是bab，为了被Accept，花了很长时间改代码使类似的case通过，但最终自己的版本仍然没有一个被通过，没意识到限定条件估计还得调很久，后来看别人的解答时才恍然意识到自己忽略了重要限定条件。另外，做这题还遇到个奇葩现象，我的方法三在Eclipse中运行ba 得到的是aba，但在leetcode中一直wrong answer，说是我的函数运行结果是bab，想不通。 最终被Accept的代码就29行，对比起来自己先前的代码真像懒婆娘的裹脚布，自己都懒得去看了，╮(╯▽╰)╭ , 效率上Method3 > Method1 > Method2 以后类似情况要及时参考下别人的解法。

[ref]
http://blog.csdn.net/xudli/article/details/45931667

public class Solution {
    public String shortestPalindrome(String s) {
        if (s == null || s.length() < 2)
            return s;
        int center = (s.length() - 1) / 2;
        String result = null;
        for (int i = center; i >= 0; i--) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                if ((result = buildPalin(s, i, i + 1)) != null)
                    return result;
            }
            if ((result = buildPalin(s, i, i)) != null)
                return result;
        }
        return null;
    }
    private String buildPalin(String s, int left, int right) {
        int n = s.length();
        while (left >= 0 && right < n) {
            if (s.charAt(left) != s.charAt(right))
                break;
            left--;
            right++;
        }
        if (left >= 0)
            return null;
        StringBuilder extra = new StringBuilder(s.substring(right));
        return extra.reverse().append(s).toString();
    }
}

    // Method 3
    public String shortestPalindrome3(String s) {
        if (s == null || s.length() < 2)
            return s;
        int n = s.length();
        int minLen = Integer.MAX_VALUE;
        String bestAns = "";
        
        int right = n / 2;
        int left = right - 1;
        String ans;
        while (true) {
            // round 1: 从中心开始，左右开弓，找到的首个以当前字符为中心且边界之前左右都相等即是这种找法下最短回文串中心点
            if (left >= 0) {
                ans = wrap(s, left, left, n, minLen);
                if (ans != null && ans.length() < minLen) {
                    minLen = ans.length();
                    bestAns = ans;
                    if (minLen == n)
                        return bestAns;
                }
                if (left + 1 < n) {
                    ans = wrap(s, left, left + 1, n, minLen);
                    if (ans != null && ans.length() < minLen) {
                        minLen = ans.length();
                        bestAns = ans;
                        if (minLen == n)
                            return bestAns;
                    }
                }
                left--;
            }
            if (right < n) {
                ans = wrap(s, right, right, n, minLen);
                if (ans != null && ans.length() < minLen) {
                    minLen = ans.length();
                    bestAns = ans;
                    if (minLen == n)
                        return bestAns;
                }
                if (right + 1 < n) {
                    ans = wrap(s, right, right + 1, n, minLen);
                    if (ans != null && ans.length() < minLen) {
                        minLen = ans.length();
                        bestAns = ans;
                        if (minLen == n)
                            return bestAns;
                    }
                }
                right++;
            }
            if (left < 0 && right >= n)
                break;
        }
        return bestAns;
    }
    
    // Method 2
    public String shortestPalindrome2(String s) {
        if (s == null || s.length() < 2)
            return s;
        int n = s.length();
        int minLen = Integer.MAX_VALUE;
        String bestAns = "";
        for (int i = 0; i < n - 1; i++) {
            // round 1: 从中心开始，左右开弓，找到的首个以当前字符为中心且边界之前左右都相等即是这种找法下最短回文串中心点
            String ans = wrap(s, i, i, n, minLen);
            if (ans != null && ans.length() < minLen) {
                minLen = ans.length();
                bestAns = ans;
            }
            // round 2: 以相邻两个字符为中心向外辐射查找最短回文串
            ans = wrap(s, i, i + 1, n, minLen);
            if (ans != null && ans.length() < minLen) {
                minLen = ans.length();
                bestAns = ans;
            }
        }
        return bestAns;
    }
    
    public String wrap (String s, int left, int right, int n, int minLen) { 
        int len = getPalin(s, left, right, n);
        if (len == n) {
            return s;
        } else if (len > 0 && len < minLen) {
            int leftLen = left != right ? (left + 1) : left;
            int rightLen = left != right ? (n - left - 1) : (n - right - 1);
            return buildPalin(s, leftLen, rightLen, n);
        }
        return null;
    }
    
    // Method 1 方向和leetcode test case不一致
    public String shortestPalindrome1(String s) {
        if (s == null || s.length() < 2)
            return s;
        int n = s.length();
        // round 1: 从中心开始，左右开弓，找到的首个以当前字符为中心且边界之前左右都相等即是这种找法下最短回文串中心点
        int left = n / 2, right = left + 1;
        int minLen = -1;
        String ans = null;
        while (left >= 0 && right < n) {
            minLen = getPalin(s, left, left, n);
            if (minLen == n)
                return s;
            if (minLen > 0) {
                ans = buildPalin(s, left, n - left - 1, n);
                break;
            } else {
                minLen = getPalin(s, right, right, n);
                if (minLen > 0) {
                    ans = buildPalin(s, right, n - right - 1, n);
                    break;
                }
            }
            left--;
            right++;
        }
        if (ans == null && left >= 0) {
            // minLen = getPalin(s, left, left, n);
            ans = buildPalin(s, left, n - left - 1, n);
        }
        
        // round 2: 以相邻两个字符为中心向外辐射查找最短回文串
        int mid = n / 2;
        for (int i = 0; i < n - 1; i++) {
            int len = getPalin(s, i, i + 1, n);
            if (len == n)
                return s;
            if (len > 0 && len < minLen) {
                int leftLen = i + 1, rightLen = n - i - 1;
                ans = buildPalin(s, leftLen, rightLen, n);
            }
        }
        return ans;
    }
    // 以left, right为中心向外辐射，某一方向能到达边界则可以以(left, right)为中心创建一个回文串
    private int getPalin(String s, int left, int right, int n) {
        int i = left, j = right;
        while (i >= 0 && j < n) {
            if (s.charAt(i--) != s.charAt(j++))
                return -1;
        }
        if (i > 0) {
            return left == right ? (2 * left + 1) : (2 * left + 2);
        } else {
            return left == right ? (2 * (n - right) - 1) : (2 * (n - right));
        }
    }
    private String buildPalin(String s, int leftLen, int rightLen, int n) {
        String ans = null;
        if (leftLen >= rightLen) {// left part is longer
            StringBuilder extraLeft = new StringBuilder(s.substring(0, leftLen - rightLen));
            StringBuilder tmp = new StringBuilder(s);
            tmp.append(extraLeft.reverse().toString());
            ans = tmp.toString();
        } else {
            StringBuilder extraRight = new StringBuilder(s.substring(n - (rightLen - leftLen), n));
            StringBuilder tmp = new StringBuilder(extraRight.reverse().toString());
            tmp.append(s);
            ans = tmp.toString();
        }
        return ans;
    }