Decode string

The Algorithm (Stack Approach)

Since the brackets can be nested (e.g., 3[a2[c]]), we need a way to "pause" our current processing when we see a [ and resume it when we see a ]. A stack is perfect for this.

1. Initialize :

2. A stack to keep track of previous strings and numbers.

3. current_str to build the string inside the current brackets.

4. current_num to build the multiplier k (handles multi-digit numbers).

5. Iterate through the string :

6. If it's a digit : Update current_num. (e.g., current_num = current_num * 10 + digit).

7. If it's [ : This signifies the start of a new section.
8. Push the current_str and current_num onto the stack.
9. Reset current_str and current_num to handle the new inner section.
10. If it's ] : This signifies the end of a section.
11. Pop the prev_str and num (repetition count) from the stack.
12. Update current_str by appending the repeated current string to prev_str.
13. Formula: current_str = prev_str + (num * current_str).
14. If it's a letter : Just append it to current_str.

Code (C++)

#include<stack>
#include<string>
class Solution {
public:
    string decodeString(string s) {
        stack<string> lets;
        stack<int> nums;
        int cur_num = 0;
        string cur_str;
        for (auto it = s.begin(); it != s.end(); ++it) {
            char c = *it;
            if (isdigit(c)) {
                cur_num = cur_num * 10 + c - '0';
            } else if (isalpha(c)) {
                cur_str += c;
            } else {
                if (c == '[') {
                    lets.push(cur_str);
                    nums.push(cur_num);
                    cur_str.clear();
                    cur_num = 0;
                } else if (c == ']') {
                    string prev_str = lets.top();
                    lets.pop();
                    cur_num = nums.top();
                    nums.pop();
                    for (int i = 0; i < cur_num; i++) { prev_str += cur_str; }
                    cur_str = prev_str;
                    cur_num = 0;
                }
            }
        }
        return cur_str;
    }
};

some optimizations

• instead of using iterator, we directly use char to traverse the string.
• we only need to reset cur_num after pushing it onto the stack ('['), since we are using the popped value k to repeat the string when we encounter ']', no need to reset it again.

#include <stack>
#include <string>

using namespace std;

class Solution {
public:
    string decodeString(string s) {
        stack<string> strStack; // Renamed for clarity
        stack<int> numStack;
        string curStr = "";
        int curNum = 0;

        // 1. Use range-based for loop for cleaner syntax
        for (char c : s) {
            if (isdigit(c)) {
                curNum = curNum * 10 + (c - '0');
            } 
            else if (c == '[') {
                strStack.push(curStr);
                numStack.push(curNum);
                // Reset for the new context
                curStr = "";
                curNum = 0;
            } 
            else if (c == ']') {
                int k = numStack.top(); 
                numStack.pop();

                string prevStr = strStack.top(); 
                strStack.pop();

                // 2. Append directly to the prefix
                // Optimization: Helps avoid multiple string reallocations
                while (k--) {
                    prevStr += curStr;
                }
                curStr = prevStr;
            } 
            else {
                // 3. Simple 'else' is sufficient given problem constraints
                curStr += c;
            }
        }
        return curStr;
    }
};