394. Decode String

---

My Solution

Solution 1

The Key Idea for Solving This Coding Question

C++ Code

class Solution {
public:
    string decodeString(string s) {
        int sIdx = 0;
        stack<char> st;

        while (sIdx < s.size()) {
            if (s[sIdx] == ']') {
                ++sIdx;  // skip ']'

                string encodedStr;
                while (!st.empty() && st.top() != '[') {
                    encodedStr.push_back(st.top());
                    st.pop();
                }
                st.pop();  // get rid of '['

                int k = 0, x = 1;
                while (!st.empty() && isdigit(st.top())) {
                    k = k + (st.top() - '0') * x;
                    x *= 10;
                    st.pop();
                }

                string decodedStr;
                while(k > 0) {
                    decodedStr += encodedStr;
                    --k;
                }

                for (int i = decodedStr.size() - 1; i >= 0; --i) {
                    st.push(decodedStr[i]);
                }
            } else {
                // s[sIdx] != ']' is true
                st.push(s[sIdx++]);
            }
        }

        string answer;
        while (!st.empty()) {
            answer = st.top() + answer;
            st.pop();
        }

        return answer;
    }
};

Time Complexity

Space Complexity

Solution 2

The Key Idea for Solving This Coding Question

C++ Code

class Solution {
public:
    string decodeString(string s) {
        int i = 0;
        return decodeString(s, i);
    }
    
private:
    string decodeString(string s, int &i) {
        string decoded;
        while (i < s.size() && s[i] != ']') {
            if (isdigit(s[i])) {
                int k = 0;
                while (i < s.size() && isdigit(s[i])) {
                    k = k * 10 + (s[i] - '0');
                    ++i;
                }
                // s[i] is '['.
                
                ++i; // skip '['.
                string encoded = decodeString(s, i);
                ++i; // skip ']'.
                
                while (k > 0) {
                    decoded += encoded;
                    --k;
                }
            } else {
                decoded.push_back(s[i++]);
            }    
        }
        
        return decoded;
    }
};

Time Complexity

Space Complexity

Solution 3

The Key Idea for Solving This Coding Question

C++ Code

class Solution {
public:
    string decodeString(string s) {
        queue<char> q;
        for (int i = 0; i < s.size(); ++i) {
            q.push(s[i]);
        }

        return decodeString(q);
    }
    
private:
    string decodeString(queue<char> &q) {
        int k = 0;
        string decoded;
        
        while (!q.empty()) {
            int c = q.front();
            q.pop();
            
            if (isdigit(c)) {
                k = k * 10 + (c - '0');
            } else if (c == '[') {
                string encoded = decodeString(q);
                while (k > 0) {
                    decoded += encoded;
                    --k;
                }
            } else if (c == ']') {
                break;
            } else {
                decoded.push_back(c);
            }
        }
        
        return decoded;
    }
};

Time Complexity

Space Complexity

Miscellaneous