394. 字符串解码（Decode String）
频次 ★★★★ · 难度 🟡 · 高频：腾讯/字节
题目
给定形如 k[encoded_string] 的编码字符串，k 表示方括号内字符串重复的次数，返回解码后的字符串。支持嵌套，如 3[a2[c]]。
示例：
输入: s = "3[a2[c]]"
输出: "accaccacc"
输入: s = "2[abc]3[cd]ef"
输出: "abcabccdcdcdef"
思路
嵌套结构天然适合用栈处理：“遇到新的一层就把当前状态保存起来，处理完内层再恢复”。用两个栈分别保存进入 [ 之前的重复次数和已拼接的字符串：
- 遇到数字：累积成
num（可能多位数，如12[...]）。 - 遇到
[：把num和当前已拼好的cur压栈，重置num = 0、cur = new StringBuilder()，开始处理新的一层。 - 遇到
]：说明一层结束，弹出对应的次数和外层字符串，把cur重复count次拼接到外层字符串后面，作为新的cur继续。 - 遇到普通字母：直接拼到
cur。
代码
public String decodeString(String s) {
Deque<Integer> countStack = new ArrayDeque<>();
Deque<StringBuilder> stringStack = new ArrayDeque<>();
StringBuilder cur = new StringBuilder();
int num = 0;
for (char c : s.toCharArray()) {
if (Character.isDigit(c)) {
num = num * 10 + (c - '0');
} else if (c == '[') {
countStack.push(num);
stringStack.push(cur);
num = 0;
cur = new StringBuilder();
} else if (c == ']') {
int count = countStack.pop();
StringBuilder prev = stringStack.pop();
for (int i = 0; i < count; i++) {
prev.append(cur);
}
cur = prev;
} else {
cur.append(c);
}
}
return cur.toString();
}复杂度
- 时间：O(n · maxK) — n 是字符串长度，最坏情况下每层展开都要重复拼接
- 空间：O(n) — 栈深度和结果字符串长度
边界条件
- 没有嵌套（如
"3[a]"）：countStack/stringStack只压入弹出一次，退化成简单的”重复拼接”。 - 多层嵌套（如
"2[3[a]]"）：每进入一层[就压栈一次，出栈顺序保证内层先展开、外层后展开，符合嵌套语义。 - 字符串中没有数字和括号（纯字母）：
num始终为 0（不影响，因为不会遇到[），所有字符直接append到cur，原样返回。
变式
- 编码规则改成”字母在前、数字在后”（如
a3[b]）：整体框架不变，只是遇到普通字母的处理逻辑保持不变，数字仍然只影响紧跟其后的[...]。 - 需要支持多位重复的组合（如
2[a]3[b]而不是嵌套）：本题的代码已经天然支持，因为每次遇到]后cur会被清空重新累积普通字符，不会和前一段混在一起。
易错点
- 数字可能不止一位（
num = num * 10 + (c - '0')），漏掉这一步会把12[a]误判成1[...]2[...]。 ]处理时要先弹出外层的次数和字符串，再把cur（内层结果）重复拼接到外层后面，顺序不能反。
面试追问
- 为什么需要两个栈而不是一个？ 因为每一层需要同时记住两个信息——“这一层要重复几次”和”这一层之前已经拼好的字符串前缀”，用两个栈分别专职记录，出栈时天然配对，不需要额外的组合/拆分逻辑；也可以用一个栈存
(count, prefix)的组合对象，效果等价，只是数据结构选择不同。 - 这题和括号匹配（20 题）有什么共同点？ 都是利用栈处理”嵌套结构”，核心思路都是”遇到开括号保存现场，遇到闭括号恢复并处理当前层”；不同点是本题在恢复现场时还需要做字符串重复拼接这个额外操作，而不只是简单的匹配判断。