LeetCode 394：字符串解码——Java 单栈模拟与嵌套解析详解
一、题目描述
给定一个经过编码的字符串，编码格式为：
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. 当前字符是右括号
遇到]时，不需要将它压栈，而是立即完成一次局部解码：
弹出字符并拼接，直到栈顶是
[；弹出左括号；
继续弹出左括号前连续的数字；
将括号内字符串重复指定次数；
把展开后的新字符串重新压栈。
四、如何恢复括号内字符串
假设栈顶依次是字符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]]：
遇到内部第一个
]，将2[c]解码为cc并压栈；此时外层内容在逻辑上变成
3[acc]；遇到外层
]，再把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. 最后直接顺序弹栈拼接
最终弹栈顺序仍然与原顺序相反，因此需要将弹出的片段放到结果字符串前面。
十一、总结
字符串解码的核心，是利用栈处理括号嵌套的“后进先出”关系。遍历过程中，除右括号外的字符全部入栈；每遇到一个]，就依次弹出括号内字符串、左括号和重复次数，完成一次最内层解码，再把结果压回栈中。