Hot 100 --- 字符串解码

本文概览：本文讲解字符串解码的核心思路：用辅助栈处理嵌套括号，遇到 [ 入栈，遇到 ] 出栈并重复拼接

一、题目

二、题目分析

1. 题目要求

题目给定一个经过编码的字符串，编码规则为：k[encoded_string]，表示方括号内部的 encoded_string 正好重复 k 次。

比如：

"3[a]" → "aaa"
"3[a]2[bc]" → "aaabcbc"
"3[a2[c]]" → "accaccacc"

2. 手动解码过程

简单例子："3[a]2[bc]"

第 1 步：看到 3，后面的 [] 内容要复制 3 遍
第 2 步：看到 [，进入括号内部
第 3 步：看到 a，记录当前字符串 = "a"
第 4 步：看到 ]，退出括号，"a" 重复 3 遍 → "aaa"
第 5 步：看到 2，后面的 [] 内容要复制 2 遍
第 6 步：看到 [，进入括号内部
第 7 步：看到 bc，记录当前字符串 = "bc"
第 8 步：看到 ]，退出括号，"bc" 重复 2 遍 → "bcbc"
第 9 步：拼接 → "aaa" + "bcbc" = "aaabcbc"

复杂例子："3[a2[c]]"

第 1 步：看到 3，记录倍数 = 3
第 2 步：看到 [，进入第一层括号
第 3 步：看到 a，记录当前字符串 = "a"
第 4 步：看到 2，记录倍数 = 2
第 5 步：看到 [，进入第二层括号（嵌套了！）
第 6 步：看到 c，记录当前字符串 = "c"
第 7 步：看到 ]，退出第二层括号，"c" 重复 2 遍 → "cc"
第 8 步：拼接 → "a" + "cc" = "acc"
第 9 步：看到 ]，退出第一层括号，"acc" 重复 3 遍 → "accaccacc"

3. 核心观察：为什么用栈？

从上面的例子可以看出，当 [] 内部还出现 [] 时（嵌套括号），我们需要：

记录外层的倍数和字符串（比如第一层的 3 和 "a"）
处理内层的重复（比如第二层的 2 和 "c"）
内层处理完后，回到外层继续（把 "cc" 拼到 "a" 后面，再整体重复 3 遍）

这就是栈的特性：后进先出。后出现的括号先处理完，然后回到外层的上下文继续处理。

栈的作用：

遇到 [：把当前的倍数和字符串入栈，重置为新的上下文
遇到 ]：出栈，用倍数重复当前字符串，拼接到出栈的字符串后面

三、思路概览

public String decodeString(String s) {
    StringBuilder res = new StringBuilder();
    int multi = 0;
    Stack<Integer> stack_multi = new Stack<>();
    Stack<StringBuilder> stack_res = new Stack<>();
    
    for (char c : s.toCharArray()) {
        if (c == '[') {
            stack_multi.push(multi);
            stack_res.push(res);
            multi = 0;
            res = new StringBuilder();
        } else if (c == ']') {
            StringBuilder tmp = res;
            res = stack_res.pop();
            int curMulti = stack_multi.pop();
            for (int i = 0; i < curMulti; i++) {
                res.append(tmp);
            }
        } else if (Character.isDigit(c)) {
            multi = multi * 10 + (c - '0');
        } else {
            res.append(c);
        }
    }
    return res.toString();
}

思路简要说明：

两个栈：stack_multi 存倍数，stack_res 存字符串
**遇到 [**：把当前倍数和字符串入栈，重置 multi = 0，res = new StringBuilder()
**遇到 ]**：出栈，用倍数重复当前字符串，拼接到出栈的字符串后面
遇到数字：更新倍数（注意可能是多位数，比如 12）
遇到字母：直接拼接到当前字符串

四、思路详解

第一步：为什么需要两个栈？

因为我们需要同时记录两个信息：

倍数：遇到 [ 时，前面的数字就是倍数
字符串：遇到 [ 时，前面已经拼接的字符串需要保存

例子："3[a2[c]]"

处理到第一个 [ 时：
  倍数 = 3
  字符串 = ""（空）
  入栈：stack_multi = [3], stack_res = [""]
  重置：multi = 0, res = ""

处理到第二个 [ 时：
  倍数 = 2
  字符串 = "a"
  入栈：stack_multi = [3, 2], stack_res = ["", "a"]
  重置：multi = 0, res = ""

第二步：遇到 `[` 的处理

遇到 [ 意味着进入新的括号层级，需要：

把当前倍数入栈
把当前字符串入栈
重置倍数和字符串，开始处理括号内部

if (c == '[') {
    stack_multi.push(multi);  // 保存倍数
    stack_res.push(res);       // 保存字符串
    multi = 0;                 // 重置倍数
    res = new StringBuilder(); // 重置字符串
}

第三步：遇到 `]` 的处理

遇到 ] 意味着当前括号层级处理完毕，需要：

出栈倍数
出栈字符串
用倍数重复当前字符串
拼接到出栈的字符串后面

if (c == ']') {
    StringBuilder tmp = res;           // 当前括号内的字符串
    res = stack_res.pop();             // 恢复外层字符串
    int curMulti = stack_multi.pop();  // 恢复外层倍数
    for (int i = 0; i < curMulti; i++) {
        res.append(tmp);               // 重复拼接
    }
}

第四步：遇到数字的处理

数字可能是多位数（比如 12），所以需要累加：

1
2
3

if (Character.isDigit(c)) {
    multi = multi * 10 + (c - '0');
}

比如 "12[a]"：

看到 '1'：multi = 0 * 10 + 1 = 1
看到 '2'：multi = 1 * 10 + 2 = 12

第五步：遇到字母的处理

直接拼接到当前字符串：

1
2
3

else {
    res.append(c);
}

完整执行过程

以 "3[a2[c]]" 为例：

初始：res = "", multi = 0, stack_multi = [], stack_res = []

第 1 个字符 '3'：
  是数字，multi = 0 * 10 + 3 = 3

第 2 个字符 '['：
  入栈：stack_multi = [3], stack_res = [""]
  重置：multi = 0, res = ""

第 3 个字符 'a'：
  是字母，res = "a"

第 4 个字符 '2'：
  是数字，multi = 0 * 10 + 2 = 2

第 5 个字符 '['：
  入栈：stack_multi = [3, 2], stack_res = ["", "a"]
  重置：multi = 0, res = ""

第 6 个字符 'c'：
  是字母，res = "c"

第 7 个字符 ']'：
  tmp = "c"
  res = stack_res.pop() = "a"
  curMulti = stack_multi.pop() = 2
  重复 2 次：res = "a" + "c" + "c" = "acc"

第 8 个字符 ']'：
  tmp = "acc"
  res = stack_res.pop() = ""
  curMulti = stack_multi.pop() = 3
  重复 3 次：res = "" + "acc" + "acc" + "acc" = "accaccacc"

遍历结束，返回 "accaccacc" ✓

再以 "3[a]2[bc]" 为例：

初始：res = "", multi = 0, stack_multi = [], stack_res = []

第 1 个字符 '3'：
  multi = 3

第 2 个字符 '['：
  入栈：stack_multi = [3], stack_res = [""]
  重置：multi = 0, res = ""

第 3 个字符 'a'：
  res = "a"

第 4 个字符 ']'：
  tmp = "a"
  res = stack_res.pop() = ""
  curMulti = stack_multi.pop() = 3
  重复 3 次：res = "" + "a" + "a" + "a" = "aaa"

第 5 个字符 '2'：
  multi = 2

第 6 个字符 '['：
  入栈：stack_multi = [2], stack_res = ["aaa"]
  重置：multi = 0, res = ""

第 7 个字符 'b'：
  res = "b"

第 8 个字符 'c'：
  res = "bc"

第 9 个字符 ']'：
  tmp = "bc"
  res = stack_res.pop() = "aaa"
  curMulti = stack_multi.pop() = 2
  重复 2 次：res = "aaa" + "bc" + "bc" = "aaabcbc"

遍历结束，返回 "aaabcbc" ✓

五、总结

字符串解码的核心思路：

用两个栈：stack_multi 存倍数，stack_res 存字符串
**遇到 [**：入栈当前倍数和字符串，重置为新的上下文
**遇到 ]**：出栈，用倍数重复当前字符串，拼接到出栈的字符串后面
遇到数字：累加倍数（注意多位数）
遇到字母：直接拼接到当前字符串

栈的作用：处理嵌套括号，后进先出，内层括号先处理完，然后回到外层继续。

时间复杂度 O(n)，空间复杂度 O(n)。