LeetCode71 - 字符串解码 | 很多时候不懂事

📝 题目描述

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

测试用例保证输出的长度不会超过 10^5。

示例：

示例 1：

输入：s = "3[a]2[bc]"
输出："aaabcbc"

示例 2：

输入：s = "3[a2[c]]"
输出："accaccacc"

示例 3：

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

示例 4：

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

提示：

1 <= s.length <= 30
s 由小写英文字母、数字和方括号 '[]' 组成
s 保证是一个有效的输入
s 中所有整数的取值范围为 [1, 300]

💡 解题思路

方法一：栈操作

将解码过程看作是维护当前状态：res（当前正在拼接的字符串）和 digital（当前正在计算的倍数）。

遇到数字：累加计算当前倍数 digital。
遇到 [（保存现场）：这意味着要开启一个全新的内部字符串了。所以你要把外层的倍数 digital 压入数字栈，把外层已经拼接好的前缀字符串 res 压入字符串栈。然后清空 digital 和 res，干干净净地去处理括号里的内容。
遇到字母：直接追加到当前的 res 中。
遇到 ]（恢复现场并合并）：此时当前的 res 就是括号里需要被重复的子串。你从数字栈弹出一个倍数，把当前的 res 重复该倍数次；然后从字符串栈中弹出之前暂存的外层前缀，将两者拼接在一起，重新赋值给 res。

方法二：递归

思路：把 [...] 看作一个子问题

在遇到嵌套结构 3[a2[c]] 时，我们可以这样想：

外层在解析到 3[ 的时候，其实它并不知道里面有多复杂。
它只需要大喊一声：“谁能帮我把括号里面的内容解码出来？”
等到内部把 a2[c] 解码成 accacc 交给它，外层只需要把它重复 3 次就行了。

因此，遇到 [ 就进入递归（开启子问题），遇到 ] 就结束递归（返回子问题的结果）。

这里有一个极其关键的细节：我们需要一个全局指针（或引用参数 int& ptr）来记录当前解析到了字符串的哪个位置。这样，当内层递归处理完 2[c] 退出来时，外层才能知道接下来的字符该从哪里继续读。

🔧 代码实现

1、栈操作

class Solution {
public:
    string decodeString(string s) {
        // 存放重复次数
        stack<int> nums_stack;
        // 暂存字符串
        stack<string> str_stack;
        // 解码过程中记录的数字
        int digital = 0;
        // 返回的答案
        string res;

        for (int i = 0; i < s.size(); i++) {
            if (s[i] >= '0' && s[i] <= '9') {
                // 数字可能不止一位
                digital *= 10;
                digital += s[i] - '0';
            } else if (s[i] == '[') {
                // 遇见开头，则将手头数字、字符串入栈
                nums_stack.push(digital);
                digital = 0;
                str_stack.push(res);
                res = "";
            } else if (s[i] == ']') {
                // 遇见结尾，弹出数字栈内的内容
                int num_temp = nums_stack.top();
                nums_stack.pop();
                // 弹出先前存放的字符串
                string str_temp = str_stack.top();
                str_stack.pop();

                //重复 num_temp 次
                for (int j = 0; j < num_temp; j++) {
                    str_temp += res;
                }

                // 恢复答案字符串
                res = str_temp;
            } else {
                // 遇见字母，直接加入当前字符串
                res += s[i];
            }
        }

        return res;
    }
};

2、递归

class Solution {
public:
    string decodeString(string s) {
        int ptr = 0; // 全局索引，记录当前遍历到字符串的哪个位置
        return dfs(s, ptr);
    }

private:
    string dfs(const string& s, int& ptr) {
        string res = ""; // 当前这一层的解码结果
        int multi = 0;   // 当前这一层的倍数

        while (ptr < s.length()) {
            char c = s[ptr];

            if (isdigit(c)) {
                // 1. 遇到数字：累加计算倍数
                multi = multi * 10 + (c - '0');
                ptr++;
            } 
            else if (c == '[') {
                // 2. 遇到 '['：开启子问题
                ptr++; // 跳过 '['，让子递归从括号里面的第一个字符开始读
                string subStr = dfs(s, ptr); // 递归获取括号内的解码结果
                
                // 递归返回后，把子串按倍数拼接到当前层的 res 中
                while (multi > 0) {
                    res += subStr;
                    multi--;
                }
                // 注意：由于上面 multi-- 了，这里 multi 自动归零，准备迎接下一个可能的倍数
                
                ptr++; // 跳过匹配的 ']'
            } 
            else if (c == ']') {
                // 3. 遇到 ']'：当前子问题结束，把解析好的结果返回给上一层
                // 注意：这里不要 ptr++，把跳过 ']' 的工作留给调用它的上一层（即上面 c == '[' 的分支）
                return res; 
            } 
            else {
                // 4. 遇到普通字母：直接拼接到当前层的 res 中
                res += c;
                ptr++;
            }
        }

        return res; // 整个字符串遍历完，返回最终结果
    }
};

📊 复杂度分析

1、栈操作

时间复杂度： $O(N)$ （N 为最终解码后字符串的长度），外层循环遍历输入字符串 $O(S)$ ，内层的 for 循环用于构建重复字符串。每个字符在最终结果中出现多少次，就会被拼接多少次，因此时间复杂度严格依赖于最终输出的长度 $O(N)$ 。
空间复杂度： $O(N)$ ，数字栈的空间取决于括号的嵌套深度 $O(H)$ （ $H$ 为括号最大深度）。字符串栈保存的是每一层括号外的“前缀字符串”，其总字符数在最坏情况下也不会超过最终字符串的长度 $N$ 。所以整体空间复杂度是 $O(N)$ 。

2、递归

时间复杂度： $O(N)$ （N 为最终解码后字符串的长度），虽然是递归，但字符串 s 中的每个字符实际上只被指针 ptr 访问了 1 次（遇到 ] 和 [ 也只是 ptr++）。耗时的大头在于字符串的重复拼接操作（res += subStr）。跟双栈法一样，最终生成的字符串有多长，拼接操作就会执行多少次。因此时间复杂度严格正比于最终生成的字符串长度 $N$ 。
空间复杂度： $O(N)$ ，递归解法的空间开销主要来自系统调用栈。递归的深度取决于输入字符串中括号的嵌套层数（比如 3[a2[b4[c]]] 深度就是 3）。最坏情况下（例如 1[1[1[1[a]]]]），递归深度为 $O(S)$ ， $S$ 为输入字符串长度。另外，每一层递归都会产生局部的 res 和 subStr，这些字符串占用的总空间量在最坏情况下也与最终输出的长度 $N$ 相关。因此综合来看，空间复杂度可以认为是 $O(N)$ 。