C++ 0ms 1 Stack solution with explanation


  • 2
    L

    Use Stack to store pair of {k,encodedString}. Traverse the string and handle cases for digit, [, ] and letters. Explanation inline with code.

    class Solution {
    public:
        string decodeString(string s) {
            using P = pair<int,string>; 
            stack<P> st;                        // stack stores pair of {k,encoded_string}
            int k = 0;                          // k-value
            string res = "";                    // result
            for (const auto& c: s) {
                if (isdigit(c))             // if char is digit, then evaluate k-value
                    k = k * 10 + c - '0';
                else if (c == '[') {          // push k, and a placeholder string on stack
                    st.push({k,""});
                    k = 0;          
                } else if (c == ']') {                  // found ']', get stack top element
                    P top = st.top(); st.pop();
                    while (top.first-- > 0) {
                        if (st.empty())              // stack empty means, '[' ']' non-nested case, so add to result directly
                            res += top.second;
                        else 
                            st.top().second += top.second;   // nested case, so append to next stack entry
                    }
                } else {
                    if (!st.empty())    
                        st.top().second += c;
                    else
                        res += c;                   // 2[abc]3[cd]ef: to handle non-encoded chars (ef), add to result directly 
                }
            }
            
            while(!st.empty()) {                // populate result if stack not empty (nested case)
                P top = st.top(); st.pop();
                while (top.first-- > 0)
                    res += top.second;
            }
            return res;
        }
    };
    

Log in to reply
 

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