leetcode热题100 P394 字符串解码

---

时间轴

时间轴

2026-03-18

init

栈

---

题目：

P394 字符串解码

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

例子：ab2[cd3[ef]], 用人脑是怎么读的？

• 外层结构ab + 2[ ... ]
• 内层cd + 3[ef]
• 最里面ef

关键点：每一层 […] 都是一个 独立子问题, 这个表达式本质是：

decode(s) = 前缀 + k * decode(子串)

当我们遇到[的时候，必须保存状态：

• 之前的字符串是啥？
• 重复次数是多少？

总结一句话：

遇到 [ 就压栈保存现场，遇到 ] 就出栈恢复现场

代码如下：

#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';
}