C++ Solution 3 ms using stack


  • 0
    M
    class Solution {
    public:
        string decodeString(string &s)
        {
            stack<char> stk;
            string final = "";
            string res;
            if(s.empty())
                return s;
            for(int i = 0; i < s.size(); i++)
            {
                if(s[i] == ']')
                {
                    string temp = "";
                    res = "";
                    while(stk.top() != '[')
                    {
                        temp =  stk.top() + temp;
                        stk.pop();
                    }
                    stk.pop();  //pop the '[' which is on top of stack
                    int n = 0, i = 0;
                    //take number and store it in variable n
                    while( !stk.empty() && isdigit(stk.top()) )
                    {
                        n = n + pow(10, i) * (stk.top() - '0');
                        i++;
                        stk.pop();
                    }
                    //repeat the string inside bracket n times
                    for(int i = 0; i < n; i++)
                        res = res + temp;
                    //push all characters one by one back to stack
                    for(int i = 0; i < res.size(); i++)
                        stk.push(res[i]);
        
                }
                else
                {
                    stk.push(s[i]);
                }
            }
            //the result in snow in stack
            while(!stk.empty())
            {
                final = final + stk.top();
                stk.pop();
            }
            reverse(final.begin(), final.end());
            return final;
        }
    };
    

Log in to reply
 

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