給定一個字符串 s，你可以通過在字符串前面添加字符將其轉換為回文串。找到并返回可以用這種方式轉換的最短回文串。

示例 1:

輸入: “aacecaaa”
輸出: “aaacecaaa”

代碼

class Solution {public int  getShortestPalindrome(String s) {//求next數組的最后一個元素char[] temp=s.toCharArray();int n=s.length();int[] next=new int[n+1];int k=-1,j=0;next[0]=-1;while (j<n){if(k==-1||s.charAt(k)==s.charAt(j)){j++;k++;next[j]=k;}else {k=next[k];}}return next[n];}public String shortestPalindrome(String s) {String t=s+'#'+new StringBuilder(s).reverse();
//將逆序字符串和原字符串拼在一起，求最長公共前綴int max=getShortestPalindrome(t);return new StringBuilder(s.substring(max)).reverse()+s;}
}