C++ Non-recursive stack solution


  • 0
    A

    26 / 26 test cases passed
    Status: Accepted
    Runtime: 0 ms

    class Solution {
    public:
        string decodeString(string s) {
            string str;
            stack<pair<string, uint>> k;
            for (uint i = 0, ii = s.size(), cnt = 0; i < ii; i++) {
                if (s[i] >= '0' && s[i] <= '9') cnt = cnt * 10 + s[i] - '0';
                else if (s[i] == '[') {
                    k.push(pair<string, uint>{"", cnt});
                    k.top().first.swap(str); // put str into stack avoiding string copy, meanwhile clear str
                    cnt = 0;
                } else if (s[i] == ']') {
                    string& ref = k.top().first;
                    for (uint j = 0, jj = k.top().second; j < jj; j++) ref += str;
                    str.swap(ref);
                    k.pop();
                } else str.push_back(s[i]);
            }
            return str;
        }
    };
    

Log in to reply
 

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