栈与队列中等1 种解法
#394字符串解码
将 k[encoded_string] 按重复次数展开，编码可以嵌套且 k 可以有多位。
#字符串#栈#递归
原题
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
测试用例保证输出的长度不会超过 105。
示例 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 <= 30s由小写英文字母、数字和方括号'[]'组成s保证是一个 有效 的输入。s中所有整数的取值范围为[1, 300]
解题主线
- 遇到左括号时保存外层结果与重复次数，并为括号内片段开启新的 StringBuilder。
- 遇到右括号时完成当前层展开，再拼接回上一层，天然支持嵌套结构。
- 读取数字时用 repeat = repeat × 10 + digit 累积多位次数。
解法 1：双栈迭代解码
次数栈保存每层 k，字符串栈保存进入括号前的前缀；闭括号时展开当前层并恢复外层。
-
时间复杂度： O(N + L)，N 为编码串长度，L 为解码后字符串长度
-
空间复杂度： O(N + L)，用于层级栈与构造中的输出字符
import java.util.ArrayDeque;
import java.util.Deque;
final class Solution {
public String decodeString(String s) {
// 两个栈按嵌套层级同步保存重复次数与进入括号前的外层前缀。
Deque<Integer> repeats = new ArrayDeque<>();
Deque<StringBuilder> prefixes = new ArrayDeque<>();
StringBuilder current = new StringBuilder();
int repeat = 0;
for (int i = 0; i < s.length(); i++) {
char character = s.charAt(i);
if (Character.isDigit(character)) {
// 十进制累积保证 12[a] 等多位重复次数被整体解析。
repeat = repeat * 10 + character - '0';
} else if (character == '[') {
// 进入内层前保存外层状态，并重置当前层的次数与片段。
repeats.push(repeat);
prefixes.push(current);
repeat = 0;
current = new StringBuilder();
} else if (character == ']') {
int times = repeats.pop();
StringBuilder expanded = prefixes.pop();
expanded.append(current.toString().repeat(times));
current = expanded;
} else {
current.append(character);
}
}
return current.toString();
}
}实现提示
- String.repeat 自 Java 11 起可用，Java 21 环境可直接使用。
边界与易错点
- 不能把每个数字字符当成独立重复次数，例如 12[a] 的次数是 12。
- 两个栈必须同步入栈和出栈，分别恢复上一层次数与字符串。
- 遗留 Stack 可用 ArrayDeque 替代。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
leetcode/src/main/java/medium/Q394_stack_decodeString.java