0ms O(n) cpp solution with stack


  • 0
    T
    string buildStr(string clip, int count){
            if(0 == count) return "";
            string substr = buildStr(clip+clip, count>>1);
            if(count & 1) return substr + clip;
            else return substr;
        }
        
        string decodeString(string s) {
            s = "1[" + s + "]";
            stack<int> sta;
            stack<string> strsta;
            const int SL = s.length();
            int cnum = 0;
            string clip = "";
            for(int i = 0; i < SL; ++i){
                if('[' == s[i]){
                    strsta.top().append(clip);
                    clip = "";
                    sta.push(cnum);
                    strsta.push("");
                    cnum = 0;
                }else if(']' == s[i]){
                    strsta.top().append(clip);
                    clip = "";
                    int curn = sta.top();
                    string curs = strsta.top();
                    sta.pop(); strsta.pop();
                    if(sta.empty()) return buildStr(curs, curn);
                    else strsta.top().append(buildStr(curs, curn));
                }else if(s[i] >= '0' && s[i] <= '9')
                    cnum = cnum * 10 + (s[i] - '0');
                else
                    clip += s[i];
            }
            return "";
        }

  • 0
    T

    A more concise solution, but a little slower.

    string buildStr(string clip, int count){
            if(0 == count) return "";
            string substr = buildStr(clip+clip, count>>1);
            if(count & 1) return substr + clip;
            else return substr;
        }
        
        string decodeString(string s) {
            s = "1[" + s + "]";
            stack<int> sta;
            stack<string> strsta;
            const int SL = s.length();
            int cnum = 0;
            for(int i = 0; i < SL; ++i){
                if('[' == s[i]){
                    sta.push(cnum);
                    strsta.push("");
                    cnum = 0;
                }else if(']' == s[i]){
                    int curn = sta.top();
                    string curs = strsta.top();
                    sta.pop(); strsta.pop();
                    if(sta.empty()) return buildStr(curs, curn);
                    else strsta.top().append(buildStr(curs, curn));
                }else if(s[i] >= '0' && s[i] <= '9')
                    cnum = cnum * 10 + (s[i] - '0');
                else
                    strsta.top().push_back(s[i]);
            }
            return "";
        }

Log in to reply
 

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