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.
strs[i] contains any possible characters out of 256 valid ASCII characters.
Follow up: Could you write a generalized algorithm to work on any possible set of characters?
Solutions
Solution 1: Encode String Length
During encoding, we convert the length of the string into a fixed 4-digit string, add the string itself, and append it to the result string in sequence.
During decoding, we first take the first four digits of the string to get the length, and then cut the following string according to the length. We cut it in sequence until we get the list of strings.
The time complexity is $O(n)$.
1 2 3 4 5 6 7 8 91011121314151617181920212223
classCodec:defencode(self,strs:List[str])->str:"""Encodes a list of strings to a single string."""ans=[]forsinstrs:ans.append('{:4}'.format(len(s))+s)return''.join(ans)defdecode(self,s:str)->List[str]:"""Decodes a single string to a list of strings."""ans=[]i,n=0,len(s)whilei<n:size=int(s[i:i+4])i+=4ans.append(s[i:i+size])i+=sizereturnans# Your Codec object will be instantiated and called as such:# codec = Codec()# codec.decode(codec.encode(strs))
publicclassCodec{// Encodes a list of strings to a single string.publicStringencode(List<String>strs){StringBuilderans=newStringBuilder();for(Strings:strs){ans.append((char)s.length()).append(s);}returnans.toString();}// Decodes a single string to a list of strings.publicList<String>decode(Strings){List<String>ans=newArrayList<>();inti=0,n=s.length();while(i<n){intsize=s.charAt(i++);ans.add(s.substring(i,i+size));i+=size;}returnans;}}// Your Codec object will be instantiated and called as such:// Codec codec = new Codec();// codec.decode(codec.encode(strs));
classCodec{public:// Encodes a list of strings to a single string.stringencode(vector<string>&strs){stringans;for(strings:strs){intsize=s.size();ans+=string((constchar*)&size,sizeof(size));ans+=s;}returnans;}// Decodes a single string to a list of strings.vector<string>decode(strings){vector<string>ans;inti=0,n=s.size();intsize=0;while(i<n){memcpy(&size,s.data()+i,sizeof(size));i+=sizeof(size);ans.push_back(s.substr(i,size));i+=size;}returnans;}};// Your Codec object will be instantiated and called as such:// Codec codec;// codec.decode(codec.encode(strs));
typeCodecstruct{}// Encodes a list of strings to a single string.func(codec*Codec)Encode(strs[]string)string{ans:=&bytes.Buffer{}for_,s:=rangestrs{t:=fmt.Sprintf("%04d",len(s))ans.WriteString(t)ans.WriteString(s)}returnans.String()}// Decodes a single string to a list of strings.func(codec*Codec)Decode(strsstring)[]string{ans:=[]string{}i,n:=0,len(strs)fori<n{t:=strs[i:i+4]i+=4size,_:=strconv.Atoi(t)ans=append(ans,strs[i:i+size])i+=size}returnans}// Your Codec object will be instantiated and called as such:// var codec Codec// codec.Decode(codec.Encode(strs));