一、题目描述

给定一个经过编码的字符串，编码格式为：

k[encoded_string]

它表示方括号中的encoded_string需要重复k次，其中k是正整数。

例如：

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

表达式3[a]解码为aaa，2[bc]解码为bcbc，拼接后得到aaabcbc。

编码还可能嵌套：

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

这里必须先把内部的2[c]解码为cc，再把外部的a2[c]还原为acc，最后重复三次。由此可以发现，本题具有明显的“后进入、先处理”特征，非常适合使用栈。

二、为什么使用栈

当我们从左到右扫描字符串时，在遇到右括号]之前，并不知道当前括号内的内容是否已经完整。因此，可以先把数字、字母和左括号依次压入栈中。

右括号]表示当前最内层表达式已经结束。此时从栈顶向前弹出，元素顺序恰好是：

括号内字符串 → 左括号 [ → 重复次数

将这一组内容解码后，再把结果压回栈中。后续如果遇到外层右括号，刚刚得到的字符串就会作为外层内容继续参与解码。

所以栈能够自然保证：

最内层括号先被处理，外层括号后被处理。

三、遍历字符串的处理规则

准备一个Stack<String>，逐个扫描输入字符串中的字符。

1. 当前字符不是右括号

数字、字母和左括号都直接压栈：

stack.push(String.valueOf(ch));

例如扫描3[a后，栈中内容为：

["3", "[", "a"]

2. 当前字符是右括号

遇到]时，不需要将它压栈，而是立即完成一次局部解码：

1. 弹出字符并拼接，直到栈顶是[；

2. 弹出左括号；

3. 继续弹出左括号前连续的数字；

4. 将括号内字符串重复指定次数；

5. 把展开后的新字符串重新压栈。

四、如何恢复括号内字符串

假设栈顶依次是字符c、b，它们原来的顺序应该是bc。由于栈是后进先出，如果直接把弹出的字符追加到末尾，就会错误地得到cb。

因此必须把每次弹出的字符放到temp前面：

String temp = ""; while (!stack.peek().equals("[")) { temp = stack.pop() + temp; }

执行过程为：

弹出 c：temp = "c" 弹出 b：temp = "b" + "c" = "bc"

当栈顶变成[时，说明当前括号内的内容已经全部取出，随后弹出左括号：

stack.pop();

五、如何解析多位重复次数

重复次数不一定只有一位，例如：

12[a]

字符1和2是分别入栈的。弹栈时会先得到2，再得到1，因此同样需要从前面拼接：

String num = ""; while (!stack.isEmpty() && Character.isDigit(stack.peek().charAt(0))) { num = stack.pop() + num; }

这样才能得到字符串"12"，而不是"21"。随后将其转换为整数：

int repeatNum = Integer.parseInt(num);

题目保证输入合法，并且k是正整数，所以标准输入中num不会为空，也不会出现重复零次的情况。

六、展开后为什么还要压回栈

得到temp和repeatNum后，将temp重复指定次数：

StringBuilder newStr = new StringBuilder(); for (int i = 0; i < repeatNum; i++) { newStr.append(temp); }

然后把结果压回栈中：

stack.push(newStr.toString());

这样既能处理多个并列表达式，也能处理嵌套表达式。

例如3[a2[c]]：

1. 遇到内部第一个]，将2[c]解码为cc并压栈；

2. 此时外层内容在逻辑上变成3[acc]；

3. 遇到外层]，再把acc重复三次。

这就是栈从内到外解析嵌套结构的过程。

七、完整 Java 代码

下面的代码严格使用截图中的单栈思路：

import java.util.Stack; class Solution { public String decodeString(String s) { Stack<String> stack = new Stack<>(); for (char ch : s.toCharArray()) { if (ch != ']') { // 数字、字母和左括号直接入栈 stack.push(String.valueOf(ch)); continue; } // 1. 取出当前最内层括号中的字符串 String temp = ""; while (!stack.peek().equals("[")) { temp = stack.pop() + temp; } // 2. 弹出左括号 stack.pop(); // 3. 解析左括号前的多位重复次数 String num = ""; while (!stack.isEmpty() && Character.isDigit(stack.peek().charAt(0))) { num = stack.pop() + num; } int repeatNum = Integer.parseInt(num); // 4. 将字符串重复指定次数 StringBuilder newStr = new StringBuilder(); for (int i = 0; i < repeatNum; i++) { newStr.append(temp); } // 5. 将局部解码结果重新压栈 stack.push(newStr.toString()); } // 栈中可能存在多个并列片段，需要按原顺序拼接 String result = ""; while (!stack.isEmpty()) { result = stack.pop() + result; } return result; } }

八、示例完整推演

以s = "3[a]2[bc]"为例。

1. 处理3[a]

扫描到第一个右括号前，栈为：

["3", "[", "a"]

遇到]：

• 弹出a，得到temp = "a"；

• 弹出[；

• 弹出数字3，得到repeatNum = 3；

• 将a重复三次，得到aaa；

• 把aaa压入栈中。

此时：

stack = ["aaa"]

2. 处理2[bc]

继续扫描2[bc后：

stack = ["aaa", "2", "[", "b", "c"]

遇到第二个]：

• 先弹出c，再弹出b，得到temp = "bc"；

• 弹出[和数字2；

• 将bc重复两次，得到bcbc；

• 把bcbc压栈。

最终栈为：

["aaa", "bcbc"]

遍历结束后，按照原顺序拼接栈中片段，得到：

"aaa" + "bcbc" = "aaabcbc"

九、复杂度分析

设最终解码字符串长度为N。每个输入字符会被压栈、弹栈，展开字符串本身还需要实际生成，因此时间复杂度可表示为O(N)。这里的N应按解码后的结果规模计算，而不能只看原字符串长度。

栈和中间字符串最多需要保存解码结果中的字符，空间复杂度为O(N)。

需要注意，代码中使用stack.pop() + temp和最终的字符串头部拼接，Java 字符串不可变，极端情况下会产生额外复制开销。但本文严格遵循截图的单栈拼接方案；若追求更高性能，可以进一步使用StringBuilder优化拼接。

十、常见错误

1. 把右括号也压入栈

右括号是触发解码的信号，遇到后应立即处理当前最内层结构。

2. 弹出的字符直接追加到末尾

栈的弹出顺序与原字符串相反，应使用：

temp = stack.pop() + temp;

否则bc会被拼成cb。

3. 只弹出一个数字

重复次数可能是多位数，必须连续弹出所有相邻数字，并注意恢复原顺序。

4. 解码结果没有重新入栈

如果不将局部结果压回栈，外层表达式就无法继续使用内层解码结果，嵌套结构会解析失败。

5. 最后直接顺序弹栈拼接

最终弹栈顺序仍然与原顺序相反，因此需要将弹出的片段放到结果字符串前面。

十一、总结

字符串解码的核心，是利用栈处理括号嵌套的“后进先出”关系。遍历过程中，除右括号外的字符全部入栈；每遇到一个]，就依次弹出括号内字符串、左括号和重复次数，完成一次最内层解码，再把结果压回栈中。