LeetCode Hot 100 P394 Decode String

---

Timeline

timeline

2026-03-18

init

stack

---

Problem:

P394 Decode String

https://leetcode.cn/problems/decode-string/description/?envType=study-plan-v2&envId=top-100-liked

Example:ab2[cd3[ef]], how does the human brain read it?

• outer structureab + 2[ ... ]
• inner layercd + 3[ef]
• innermostef

Key point: each layer […] is an independent subproblem, the essence of this expression is:

decode(s) = prefix + k * decode(substring)

When we encounter[we must save the state:

• What was the previous string?
• What is the number of repetitions?

In summary:

encounter [ then push onto stack to save context，encounter ] then pop from stack to restore context

The code is as follows:

#include <stack>
#include <string>

using std::stack;
using std::string;

class Solution {
    public:
        string decodeString(string s)
        {
                stack<int> times;
                stack<string> strs;

                string curr = "";
                int num = 0, k;

                for (char ch : s) {
                        if (ch >= '0' && ch <= '9') {
                                num = num * 10 + (ch - '0');
                        } else if (ch == '[') {
                                times.push(num);
                                strs.push(curr);
                                num = 0;
                                curr = "";
                        } else if (ch == ']') {
                                k = times.top();
                                times.pop();
                                string prev = strs.top();
                                strs.pop();

                                string tmp;
                                for (int i = 0; i < k; i++)
                                        tmp += curr;

                                curr = prev + tmp;
                        } else { // alpha
                                curr += ch;
                        }
                }

                return curr;
        }
};

#include <iostream>
int main()
{
        Solution S;
        string s1 = "2[abc]3[cd]ef";
        string s2 = "3[a2[c]]";
        string s3 = "2[2[y]pq]";

        std::cout << S.decodeString(s1) << '\n';

        std::cout << S.decodeString(s2) << '\n';

        std::cout << S.decodeString(s3) << '\n';
}