LeetCode 394：字符串解码——Java 单栈模拟与嵌套解析详解

一、题目描述给定一个经过编码的字符串编码格式为k[encoded_string]它表示方括号中的encoded_string需要重复k次其中k是正整数。例如输入s 3[a]2[bc] 输出aaabcbc表达式3[a]解码为aaa2[bc]解码为bcbc拼接后得到aaabcbc。编码还可能嵌套输入s 3[a2[c]] 输出accaccacc这里必须先把内部的2[c]解码为cc再把外部的a2[c]还原为acc最后重复三次。由此可以发现本题具有明显的“后进入、先处理”特征非常适合使用栈。二、为什么使用栈当我们从左到右扫描字符串时在遇到右括号]之前并不知道当前括号内的内容是否已经完整。因此可以先把数字、字母和左括号依次压入栈中。右括号]表示当前最内层表达式已经结束。此时从栈顶向前弹出元素顺序恰好是括号内字符串 → 左括号 [ → 重复次数将这一组内容解码后再把结果压回栈中。后续如果遇到外层右括号刚刚得到的字符串就会作为外层内容继续参与解码。所以栈能够自然保证最内层括号先被处理外层括号后被处理。三、遍历字符串的处理规则准备一个StackString逐个扫描输入字符串中的字符。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; }执行过程为弹出 ctemp c 弹出 btemp 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) { StackString 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. 最后直接顺序弹栈拼接最终弹栈顺序仍然与原顺序相反因此需要将弹出的片段放到结果字符串前面。十一、总结字符串解码的核心是利用栈处理括号嵌套的“后进先出”关系。遍历过程中除右括号外的字符全部入栈每遇到一个]就依次弹出括号内字符串、左括号和重复次数完成一次最内层解码再把结果压回栈中。