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