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.

Use an integer at the beginning of each string to record the length of this string.

abcd

5ds74

1ds

is converted to

4)abcd5)5ds743)1ds

class Codec {
public:

    // Encodes a list of strings to a single string.
    string encode(vector<string>& strs) {
        string ans;
        for(size_t i = 0; i < strs.size(); i++){
            int len = strs[i].size(); // overflow?
            ans.append(to_string(len));
            ans.push_back(')');
            ans.append(strs[i]);
        }
        return ans;
    }

    // Decodes a single string to a list of strings.
    vector<string> decode(string s) {
        vector<string> ans;
        size_t i = 0;
        while(i < s.size()){
            int len = parseLen(s, i);
            ans.push_back(s.substr(i, len));
            i = i + len;
        }
        return ans;
    }
    long parseLen(string s, size_t & i){
        int len = 0;
        while(isDigit(s[i])){
            len = len * 10 + s[i] - '0';
            i++;
        }
        i++;//ignore ')' character
        return len;
    }
    bool isDigit(char c){
        return c <= '9' && c >= '0';
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.decode(codec.encode(strs));

Or there is a more “standard” solution, escape character.

If we meet a ‘\’, add a new ‘\’ ahead of it;

If we meet a ‘,’, add a new ‘\’ ahead of it.

then we use ‘,’ to separate strings.

class Codec {
public:

    // Encodes a list of strings to a single string.
    string encode(vector<string>& strs) {
        string ans;
        for(auto it = strs.begin(); it != strs.end(); it++){
            for(int i = 0; i < (*it).size(); i++){
                char c = (*it)[i];
                if(c == '\\' || c == ','){
                    ans.push_back('\\');
                }        
                ans.push_back(c);
            }
            ans.push_back(',');
        }
        return ans;
    }

    // Decodes a single string to a list of strings.
    vector<string> decode(string s) {
        bool isEscape = false;
        vector<string> ans;
        string str;
        for(size_t i = 0; i < s.size(); i++){
            char c = s[i];
            if(isEscape){
                isEscape = false;
                str.push_back(c);
            }else{
                if(c == '\\'){
                    isEscape = true;
                }
                else if(c == ','){
                    ans.push_back(str);
                    str.clear();
                }else{
                    str.push_back(c);
                }
            }
        }
        return ans;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.decode(codec.encode(strs));