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:

It is easy to understand, the idea to solve this problem is to find the longest palindrome from beginning, and reverse the remaining string then append to the beginning of s.

So, 

s= (longest Panlindrome) + suffix;

String prefix= suffix.reverse();

return prefix+s;

1. Brute force, 

Starting from the end of the string, and keep checking the substring(0,j) until the substring is a valid palindrome, which is the longest palindrome. 

To check if it is a valid palindrome, we can do char by char comparison, or we can compare the string with its reversed string. 

Time complexity(O(n^2)

 public String shortestPalindrome(String s) {  
     if(s==null || s.length()<=1) return s;  
    int end=0;  
     for(int i=s.length()-1;i>=0;i--){  
       if(s.charAt(i)==s.charAt(0) && isPar(s,0,i)) {  
         end=i;  
         break;  
       }  
     }  
     if(end==s.length()-1) return s;  
     StringBuilder sb=new StringBuilder(s.substring(end+1,s.length()));  
     return sb.reverse().append(s).toString();  
   }  
   public boolean isPar(String s, int i, int j){  
     while(i<j){  
        if(s.charAt(i)!=s.charAt(j)) return false;  
       i++;  
       j--;  
     }  
     return true;  
   }  

2.Recursion + Two pointers
For a given string, if we start i from 0 and iterate j from n-1 to 0, if(char[i]==char[j]) we increment i,apparently, if s is a palindrome, when the iteration is over, i should be equal to s.length(); otherwise, s.substring(0,i) should contain the longest palindrome. Eg. "abcbaef" when iteration is over, i should be at the position of e, and abcba should contain the longest palindrome. eg "aabbcaa" when iteration is over, i should be at the position of 'c' and "aabb" contains the longest palindrome "aa". The proof is that if you start j from the end of the longest palindrome, when the iteration is over, i should be the position right after the end of the longest palindrome, but since we are starting j from the end of the string ,any additional match would increment i, so substring(0,i) should always contain the longest palindrome.
So we can recursively find the result with prefix+ shortestParlindrome+ suffix
Time complexity: O(n^2)

 public String shortestPalindrome(String s) {  
     if(s==null || s.length()<=1) return s;  
     int i=0;  
     for(int j=s.length()-1;j>=0;j--){  
       if(s.charAt(i)==s.charAt(j)) i++;  
     }  
     if(i==s.length()) return s;  
     String suffix=s.substring(i);  
     String prefix=new StringBuilder(suffix).reverse().toString();  
     String mid=shortestPalindrome(s.substring(0,i));  
     return prefix+mid+suffix;  
   }  

3. KMP algorithm
We can use KMP mathing table to find the longest palindrome.
eg. string s="aacecaaa"
reverse="aaacecaa",
the match of the reverse should be 1,2,2,3,4,5,6,7, which means the maximum match is reverse(1,7) to s(0,6) , so s(0,6) should be the longest palindrome starting from 0.
Use a '#' to concatenate s and its reverse and then use classic KMP to get the matching table. Leetcode has a completed solution for this problem.
Time complexity: O(n)
Because the out loop always increase j, and the inner loop always increase j-i, the maximum of j should be n and the maximum j-i should be n as well, so the time complexity should be O(n)

 public String shortestPalindrome(String s) {  
     if(s==null || s.length()==0) return s;  
     String reversed=new StringBuilder(s).reverse().toString();  
    String s2=s+"#"+reversed;  
     int[] kmp=new int[s2.length()];  
     int i=0;  
     for(int j=1;j<s2.length();j++){  
       while(i!=0 && s2.charAt(j)!=s2.charAt(i)){  
         i=kmp[i-1];  
       }  
       if(s2.charAt(j)==s2.charAt(i)) kmp[j]=++i;  
     }  
     int ind=s.length()-kmp[s2.length()-1];  
     return reversed.substring(0,ind)+s;  
   }