Shortest Palindrome

https://leetcode.com/problems/shortest-palindrome/
给定一个String，可以在这个String的前面加上特定的字符串，使结果变成一个回文串
Example 1:
Input: "aacecaaa"
Output: "aaacecaaa"
Example 2:
Input: "abcd"
Output: "dcbabcd"

暴力求解

• 原字符串为s,翻转字符串，得到t
• 如果s等于t，则结果就是s，然后逐个去掉s的后面i个字母（同时逐个去掉t的前i个字母）
• 如果两个子串相等，则表明剩下的子串就是回文，只需把t后面n-i到最后的子串加到s前面即可

//brute force
    public String shortestPalindrome2(String s) {
        String t = reverse(s, 0, s.length() - 1);
        int n = s.length();
        int i = 0;
        for (i = n; i >= 0; i--) {
            if (s.substring(0, i).equals(t.substring(n - i))) {
                break;
            }
        }
        return t.substring(0, n - i) + s;
    }

解法2

递归方法，先找出这个string的最长回文子串（也许不存在，此时会出现一种特殊的情况）。然后把最长回文子串的其他部分复制。

talk is cheap，show me your example

Input: "aacecaaa"
------------------------------
i = 0,j = 7   s.charAt(0) == s.charAt(7)
------------------------------
i = 1,j = 6   s.charAt(1) == s.charAt(6)
------------------------------
i = 2,j = 5   s.charAt(2) != s.charAt(5)
------------------------------
i = 2,j = 4   s.charAt(2) == s.charAt(4)
------------------------------
i = 3,j = 3   s.charAt(3) == s.charAt(3)
------------------------------
i = 4,j = 2   s.charAt(4) == s.charAt(2)
------------------------------
.....
------------------------------
i = 7,j = 8
------------------------------
rem = s.substring(7,8) = 'a';
rem_rev = 'a';
res = 'a' + func(s.substring(0,7)) + 'a'; // ('a' + 'aacecaa' + 'a')

注意这个i算出来的结果，不一定是回文串，即s.substring(0,i)可能并不是一个回文，所以需要一个fun(s.substring(0,i))来再算一遍
用这个example可以说明， s="adcba" , 用func后，并没有回文子串，得到的i是2，所以次数的rem = "cba",rem_rev = "abc" ，而s.substring(0,2) = "ad"需要再来一遍

 public String shortestPalindrome(String s) {
        int i = 0, n = s.length();
        for (int j = n - 1; j >= 0; --j) {
            if (s.charAt(i) == s.charAt(j)) {
                ++i;
            }
        }
        if (i == n) {
            return s;
        }
        String rem = s.substring(i);
        String rem_rev = new StringBuilder(rem).reverse().toString();
        return rem_rev + shortestPalindrome(s.substring(0, i)) + rem;
    }