Leetcode 271 Encode and Decode Strings

Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.

Machine 1 (sender) has the function:

string encode(vector<string> strs) {
  // ... your code
  return encoded_string;
}

Machine 2 (receiver) has the function:

vector<string> decode(string s) {
  //... your code
  return strs;
}

So Machine 1 does:

string encoded_string = encode(strs);

and Machine 2 does:

vector<string> strs2 = decode(encoded_string);

strs2 in Machine 2 should be the same as strs in Machine 1.

Implement the encode and decode methods.

Note:

• The string may contain any possible characters out of 256 valid ascii characters. Your algorithm should be generalized enough to work on any possible characters.
• Do not use class member/global/static variables to store states. Your encode and decode algorithms should be stateless.
• Do not rely on any library method such as eval or serialize methods. You should implement your own encode/decode algorithm.

Solution 1: Use KMP, insert needles between the String to Serialize. 

 public class Codec {  
   String needle="#21kmpd#";  
   // Encodes a list of strings to a single string.  
   public String encode(List<String> strs) {  
     StringBuilder sb=new StringBuilder();  
     for (String s: strs) {  
       sb.append(s);  
       sb.append(needle);  
     }  
     return sb.toString();  
   }  
   // Decodes a single string to a list of strings.  
   public List<String> decode(String s) {  
     int n=s.length();  
     int m=needle.length();  
     int[] next=new int[m];  
     List<String> res=new ArrayList<>();  
     next[0]=-1;  
     int k=-1, j=0;  
     while (j<m-1) {  
       if (k==-1 || needle.charAt(j)==needle.charAt(k)) {  
         j++;  
         k++;  
         next[j]=needle.charAt(j)==needle.charAt(k)?next[k]:k;  
       }  
       else k=next[k];  
     }  
     int i=0;  
     while (i<n) {  
       int pre=i;   
       j=0;  
       while (j<m && i<n) {  
         if (j==-1 || s.charAt(i)==needle.charAt(j)) {  
           i++;  
           j++;  
         }  
         else j=next[j];  
       }  
       res.add(s.substring(pre,i-j));  
     }  
     return res;  
   }  
 }  

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;  
   }  
 }  

Leetcode 28 Implement strStr()

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Update (2014-11-02):
The signature of the function had been updated to return the index instead of the pointer. If you still see your function signature returns a char * or String, please click the reload button  to reset your code definition.

Solution 1: Use brute force. two pointers.

 public class Solution {  
   public int strStr(String haystack, String needle) {  
     int n=haystack.length(), m=needle.length();  
     if (m==0) return 0;  
     int i=0, j=0;  
     while (i<n && j<m) {  
       if (haystack.charAt(i)==needle.charAt(j)) {  
         i++;  
         j++;  
       }  
       else {  
         i=i-j+1;  
         j=0;  
       }  
     }  
     if (j==m) return i-m;  
     return -1;  
   }  
 }  

Solution 2: KMP

 public class Solution {  
   public int strStr(String haystack, String needle) {  
     int n=haystack.length(), m=needle.length();  
     if (m==0) return 0;  
     int[] next=new int[m];  
     next[0]=-1;  
     int j=0, k=-1;  
     while (j<m-1) {  
       if (k==-1 || needle.charAt(j)==needle.charAt(k)) {  
         k++;  
         j++;  
         next[j]=(needle.charAt(j)==needle.charAt(k))?next[k]:k;  
       }  
       else k=next[k];  
     }  
     int i=0;  
     j=0;  
     while (i<n && j<m) {  
       if (j==-1 || haystack.charAt(i)==needle.charAt(j)) {  
         i++;  
         j++;  
       }  
       else j=next[j];  
     }  
     if (j==m) return i-m;  
     return -1;  
   }  
 }