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

本题的递归做法我并没有发现什么窍门，只知道这么做是每次把不包含重复字符的外边界点复制到字符串左面，然后递归一次剩余的字符串，直到该字符串整体为palindrome为止，代码如下：

 1 public class Solution {
 2     public String shortestPalindrome(String s) {
 3         int j=0;
 4         for(int i=s.length()-1;i>=0;i--){
 5             if(s.charAt(i)==s.charAt(j)) j++;
 6         }
 7         if(j==s.length()) return s;
 8         String suffix = s.substring(j);
 9         return new StringBuilder(suffix).reverse().toString()+shortestPalindrome(s.substring(0,j))+suffix;
10     }
11 }

还有kmp算法，这个算法挺好的，高端，但是难以掌握。。我没掌握下来，算法我放在了随笔里面