Decode String

394. 字符串解码

分析

使用两个栈：
- 一个存储重复次数 nums
- 一个存储当前解码过程中尚未完成的字符串 strs
遍历输入字符串 s：
- 如果是数字字符 isdigit()，将其加入当前数字 num，用于解析多位数字
- 如果是左括号 '['，将当前数字 num 和当前字符串 str 压栈，并重置 num 和 str
- 如果是右括号 ']'：
  - 弹出栈顶的数字 n（重复次数）
  - 弹出栈顶的字符串（上一级未完成的字符串）
  - 将当前字符串重复 n 次后附加到弹出的字符串中，作为当前解码结果
- 如果是普通字符，直接加入当前字符串 str
最后返回构造好的字符串

时间复杂度

每个字符都会被处理一次，栈操作均为 O(1) ，总时间复杂度 O(n^2)

空间复杂度

需要两个栈来存储数字和字符串，栈的最大深度取决于嵌套层数，空间复杂度为 O(m)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49


class Solution
{
public:
    string decodeString(string s)
    {
        // 栈 nums 保存每段的重复次数，栈 strs 保存每段解码的部分字符串
        std::stack<int> nums;
        std::stack<std::string> strs;

        int num = 0;         // 当前数字（重复次数）
        std::string str;     // 当前构造的字符串
        for (int i = 0; i < s.size(); ++i)
        {
            if (std::isdigit(s[i]))
            {
                // 累积数字，支持多位数字解析
                num = num * 10 + s[i] - '0';
            }
            else if (s[i] == '[')
            {
                // 遇到 '['，将当前数字和字符串压栈
                nums.push(num);
                strs.push(str);
                num = 0;  // 重置 num
                str = ""; // 重置当前字符串
            }
            else if (s[i] == ']')
            {
                // 遇到 ']'，进行解码
                int n = nums.top(); // 获取当前的重复次数
                nums.pop();

                std::string cur = str; // 当前字符串
                str = strs.top();     // 获取上一层未完成的字符串
                strs.pop();

                // 将当前字符串重复 n 次并追加到上一层字符串后
                while (n--)
                    str += cur;
            }
            else
            {
                // 普通字符直接追加到当前字符串中
                str += s[i];
            }
        }
        return str;
    }
};