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 strs) { // ... your code return encoded_string; } Machine 2 (receiver) has the function: vector decode(string s) { //... your code return strs; } So Machine 1 does:

string encoded_string = encode(strs); and Machine 2 does:

vector 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. Show Company Tags Show Tags Show Similar Problems

S1: running length encoding

关键是合并后如何分割各个string，如果用普通字符分隔，可能与原string中的该字符混淆。用RLE，在分隔处加上每个string的长度，便可知下个string从哪开始。为了区别记录长度的字符和string里的字符，在长度后再加一字符以示长度字符串结束。

    // Encodes a list of strings to a single string.
    string encode(vector<string>& strs) {
        string s = "";
        for(auto str: strs){
            int size = str.size();
            s += to_string(size) + '@' + str;
        }
        return s;
    }

    // Decodes a single string to a list of strings.
    vector<string> decode(string s) {
        int start = 0;
        vector<string> strs;
        while(start < s.size()){
            int pos = s.find_first_of('@', start);
            int size = stoi(s.substr(start, pos-start));
            strs.push_back(s.substr(pos+1, size));
            start = pos + size + 1;
        }
        return strs;
    }

S2: escaping charactor

定义一个分隔符’;‘,为了区分分隔符和string里的’;‘，再定义一个转义字符'@'，原string里的’;‘变为’@;‘, ‘@’变为‘@@’。(注意c中’\‘是转义字符，若要定义’\'要用'\'才能通过)

    // Encodes a list of strings to a single string.
    string encode(vector<string>& strs) {
        string s = "";
        for(auto str: strs){
           for(int i = 0; i < str.size(); ++i){
                if(str[i] == '@' || str[i] == ';') {
                    s += '@';
                }
                s += str[i];
            }
            s += ';'; 
        }
        return s;
    }

    // Decodes a single string to a list of strings.
    vector<string> decode(string s) {
        int start = 0, end = 0;
        vector<string> strs;
        string str = "";
        for(int i = 0; i < s.size(); ++i){
            if(s[i] == '@'){
                str += s[++i];    
            }
            else if(s[i] == ';'){
                strs.push_back(str);
                str = "";
            }
            else str += s[i];
        }
        return strs;
    }