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

Solution 1: use KMP calculate next array. If R is the reverse of s. Make a combo string which is s+'#'+R.

 public class Solution {  
   public String shortestPalindrome(String s) {  
     int n=s.length();  
     if (n==0) return "";  
     StringBuilder sb=new StringBuilder(s);  
     String combo=s+'#'+sb.reverse().toString();  
     int[] next=new int[2*n+2];  
     next[0]=-1;  
     int j=0, k=-1;  
     while (j<2*n+1) {  
       if (k==-1 || combo.charAt(k)==combo.charAt(j)) {  
         k++;  
         j++;  
         next[j]=k;  
       }  
       else k=next[k];  
     }  
     StringBuilder res=new StringBuilder(s.substring(next[2*n+1]));  
     return res.reverse().toString()+s;  
   }  
 }  

Solution 2: calculate next array of s, then search in R. O(n)

 public class Solution {  
   public String shortestPalindrome(String s) {  
     int n=s.length();  
     if (n<2) return s;  
     int[] next=new int[n];  
     int k=-1,j=0;  
     next[0]=-1;  
     while (j<n-1) {  
       if (k==-1 || s.charAt(k)==s.charAt(j)) {  
         k++;  
         j++;  
         next[j]=s.charAt(k)==s.charAt(j)?next[k]:k;  
       }  
       else k=next[k];  
     }  
     String r=new StringBuilder(s).reverse().toString();  
     int i=0;  
     j=0;  
     while (i<n && j<n) {  
       if (j==-1 || r.charAt(i)==s.charAt(j)) {  
         i++;  
         j++;  
       }  
       else j=next[j];  
     }  
     return new StringBuilder(s.substring(j)).reverse().toString()+s;  
   }  
 }  

Solution 3: optimize space and time complexity to be half of solution 2.

 public class Solution {  
   public String shortestPalindrome(String s) {  
     int n=s.length();  
     if (n<2) return s;  
     int[] next=new int[n/2];  
     int k=-1,j=0;  
     next[0]=-1;  
     while (j<n/2-1) {  
       if (k==-1 || s.charAt(k)==s.charAt(j)) {  
         k++;  
         j++;  
         next[j]=s.charAt(k)==s.charAt(j)?next[k]:k;  
       }  
       else k=next[k];  
     }  
     String r=new StringBuilder(s).reverse().toString();  
     int i=0;  
     j=0;  
     while (i+j<n) {  
       if (j==-1 || r.charAt(i)==s.charAt(j)) {  
         i++;  
         j++;  
       }  
       else j=next[j];  
     }  
     return r.substring(0,i-j)+s;  
   }  
 }