C++ 0ms iterative solution using a stack


  • 0
    class Solution {
    private:
        string getNext(string& s, int& i) {         // get next string, may be number / ] / regular string
            int start = i++;
            string ans = "";
            
            if (isdigit(s[start])) {
                while (i < s.length() && isdigit(s[i])) { i++; }
            } else if (s[start] != ']') {
                while (i < s.length() && !isdigit(s[i]) && s[i] != ']') { i++; }
            }
            
            ans = s.substr(start, i - start);
            if (isdigit(ans[0])) { i++; }           // i++ to skip '[' for number case
            return ans;
        }
        
    public:
        string decodeString(string s) {
            int i = 0;
            stack<string> st;
            
            while (i < s.length()) {
                string cur = getNext(s, i);
                
                if (isdigit(cur[0])) {
                    st.push(cur);
                } else {
                    if (cur == "]") {               // meaning st must have string and number as top two elements
                        string temp = st.top(); st.pop();       // get the regular string
                        cur = "";                               // clear cur string
                        int n = stoi(st.top()); st.pop();       // get the number n
                        while (n--) { cur += temp; }            // repeat last string n times
                    }
                    
                    if (st.size() && !isdigit(st.top()[0])) {
                        st.top() += cur;                        // if st.top() is also a regular string, combine it
                    } else {
                        st.push(cur);                   
                    }
                }
            }
            
            return st.size() ? st.top() : "";
        }
    };
    

Log in to reply
 

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