0ms C++ Solution With Stack, Straightforward!


  • 0
    S

    Just a very straightforward idea:

    • we push the repeat time and repeat string into the stack when meeting a '[';

    • we get the both above from the stack when meeting a ']';

    • when the stack is empty, this block has been repeated, just get the next block; otherwise, store the string, and do next repeating.

    class Solution {
    public:
        string decodeString(string s) {
            int len = s.size();
            stack<int> times; 
            stack<string> repeater;
            string lnum;                // the number on the left
            string rp;                  // the repeat string
            string ret;
            for (int i=0; i<len; i++) {
                if (isdigit(s[i])) {
                    lnum += s[i];
                    continue;
                }
                else if (isalpha(s[i])) {
                    rp += s[i];
                    continue;
                }
                else if (s[i] == '[') {
                    times.push(stoi(lnum));
                    repeater.push(rp);
                    lnum = "";
                    rp = "";
                    continue;
                }
                else if (s[i] == ']') {
                    int t = times.top();
                    times.pop();
                    string r = repeater.top();
                    repeater.pop();
          // repeat string, and store it or not.
                    for (int j=0; j<t; j++)
                        r += rp;
                    rp = r;
        // a block has been repeated, blocks just like  "2[a]2[b]" => 2[a], 2[b]
                    if (times.empty()) {
                        ret += rp;
                        rp = "";
                    }
                    continue;
                }
            }
    
    // process the trailing string, and if there is not a trail, rp = "".
            return ret+rp;
        }
    };
    

    PS:
    I wonder if there is a quite clear solution using recursion.


Log in to reply
 

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