Accepted simple C++ solution


  • 33
    S

    The rule is, for each str in strs, encode it as <length> + '@' + str

    class Codec {
    public:
    
        // Encodes a list of strings to a single string.
        string encode(vector<string>& strs) {
            string encoded = "";
            for (string &str: strs) {
                int len = str.size();
                encoded += to_string(len) + "@" + str;
            }
            
            return encoded;
        }
    
        // Decodes a single string to a list of strings.
        vector<string> decode(string s) {
            vector<string> r;
            int head = 0;
            while (head < s.size())    {
                int at_pos = s.find_first_of('@', head);
                int len = stoi(s.substr(head, at_pos - head));
                head = at_pos + 1;
                r.push_back(s.substr(head, len));
                head += len;
            }
            
            return r;
        }
    };
    
    // Your Codec object will be instantiated and called as such:
    // Codec codec;
    // codec.decode(codec.encode(strs));

  • 1
    M

    what if str itself contains @


  • 0

    Ha, mine's almost exactly the same, only real difference being this in decode (I renamed my variables to match yours):

            int len = atoi(&s[head]);
            head = s.find('@', head) + 1;
    

  • 3
    S

    @magict4 It does not matter because, for each encoded string, decode only looks for the first @ char and then read the whole string as a whole: even though the string has @ char in it, it is considered as a part of the string as decoder knows the length of the string.


  • 0
    Z

    I think this is serialize and deserialize, similar to serialize and deserialize binary tree.


  • 0
    S

    @StefanPochmann Nice, I thought atoi can only accept the C string ending with \0 character. But the c++ reference says "The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function."


  • 3
    W

    same idea but a little different :)

    class Codec {
    public:
    
        // Encodes a list of strings to a single string.
        string encode(vector<string>& strs) {
        string res;
        for(auto i:strs)
            res=res+to_string(i.size())+"#"+i;
        return res;
        }
    
        // Decodes a single string to a list of strings.
        vector<string> decode(string s) {
        vector<string> res;
        while(!s.empty())
        {
            int pos=s.find_first_of('#');
            int length=stoi(s.substr(0,pos));
            res.push_back(s.substr(pos+1,length));
            s=s.substr(length+pos+1);
        }
        return res;
        }
    };

  • 0
    L

    I got the same question as @magict4 asked. What if str itself contains @? eg. there is a string exists as "4@"; Surely wrong result may be generated from decade stage.


  • 2
    V

    @lzjknight No it won't . If the str itself is 4@, the encoding would be 2@4@ . When decoding , first you know the size is 2 , then you do a substr(2,2) , you get your 4@ , then you're done.


  • 0
    4

    Is the complexity of decoding is O(n * m)?
    n = number of words
    m = length of the encoded string
    ( find_first_of will cost m each time and it will be called n times I suppose )


  • 0
    S

    @anujbora Yes, because it has read all the characters in each word.


  • 0
    S

    I don't think that we are allowed to use "@" or any other character. what if you have "5@", in the given strings?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.