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".
解题思路：
本题最简单的思路是从后往前判断子串是否是回文串，然后把后面的弄到前面即可，不过这样仅仅能擦边通过测试，最高效的当然是KMP算法了，
KMP可以参考Java for LeetCode 028 Implement strStr()
JAVA实现如下；
public String shortestPalindrome(String s) {
for(int i=s.length();i>=1;i--)
if(isPalindrome(s.substring(0, i)))
return new StringBuilder(s.substring(i)).reverse()+s;
return "";
}
static boolean isPalindrome(String s){
int left=0,right=s.length()-1;
while(left<right)
if(s.charAt(left++)!=s.charAt(right--))
return false;
return true;
}