Run-length Encoding solution using C++


  • 1
    T

    https://en.wikipedia.org/wiki/Run-length_encoding

    The trick is, for a valid char, we only compress up to 254 occurences - count 255 means end of a string.

    typedef unsigned char UCHAR;
    const static int MAX_CNT = 255;
    
    // Encodes a list of strings to a single string.
    string encode(vector<string>& strs) {
        string ret;
        for(auto &s : strs)
        {
            int i = 0, len = s.length();
            
            while(i < len)
            {
                UCHAR c = s[i];
                UCHAR cnt = 1;
                while(i < len - 1 && s[i + 1] == c && cnt < (MAX_CNT - 1))
                {
                    i ++; cnt ++;
                }
                ret += UCHAR(cnt);
                ret += UCHAR(c);
                
                i ++;
            }
            ret += UCHAR(MAX_CNT); // 0xFF: end
        }
        return ret;
    }
    
    // Decodes a single string to a list of strings.
    vector<string> decode(string s) 
    {
        vector<string> ret;
    
        size_t len = s.length();
        string cur; int inx = 0;
        while(inx < len)
        {
            UCHAR cnt = s[inx];
            if(cnt == UCHAR(MAX_CNT))
            {
                ret.push_back(cur);
                cur = "";
                inx ++;
                continue;
            }
            //
            UCHAR c = s[inx + 1];
            for(UCHAR i = 0; i < cnt; i ++)    cur += c;
            inx += 2;                        
        }
        return ret;
    }
    

  • 0
    Y

    In the problem, it said "The string may contain any possible characters out of 256 valid ascii characters". You are using (char)255 as separator which may also occurs in some string in input list


  • 0
    T

    That's not a problem. The counter will always be decoded as a counter, instead of a char in the string, since I do decoding info into 2 parts separately: counter and chars.


  • 0
    Y

    okay, what if the input vector only contains one string with length 255


  • 0
    Y

    for example a string contains 255 character 'A'


  • 0
    T

    There will be 2 pieces of information: first piece contains a section with maximum of 254 chars in it; second piece then contains only 1 char. e.g. if there are 255 'a', it will be 254-a-1-a


Log in to reply
 

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