LeetCode 394. 字符串解码
题目描述
题意分析
编码
k[内容]表示把方括号内的内容连续重复k次，再与前后其他内容依次拼接。括号内还可以包含同样的编码，所以必须先解开内层，再决定外层实际要重复的完整内容。重复次数可能有多位，普通字母可以出现在括号内外，相邻编码段之间也不一定有分隔符。题目保证输入有效、括号匹配，数字只表示重复次数，不是要保留在输出中的普通字符。
解法：双栈解析嵌套表达式
核心思路
[!blue]
从左向右扫描时，如果没有嵌套，只需记住当前结果和重复次数。遇到内层括号后，外层还没有结束，它已经积累的前缀和重复次数都必须暂存；内层完成时，又必须先恢复最近暂存的那一层。这个后进先出的顺序正好对应栈。
用
cur保存当前层已经解码完成的内容，用count累积紧接在[前面的次数。数字逐位读取，所以遇到新数字要执行count = count * 10 + digit，而不是覆盖原来的计数。遇到
[时，把当前count压入次数栈，把当前cur压入前缀栈，两项共同记录这一层的恢复信息。随后将计数清零，并使用新的空缓冲区处理括号内部。这样内层追加字符时不会覆盖外层已经保存的内容。遇到
]时，当前cur已经是这一对括号内完整的解码结果。弹出对应的次数repeat和外层前缀prev，把cur重复追加到prev末尾，再令cur = prev。新cur就恢复为外层目前已经完成的结果，可以继续接上同层后面的字符或编码段。普通字母直接追加到
cur。每个右括号只与栈顶保存的最近一个左括号配对，因此嵌套层次不会混淆；所有字符处理完后，栈中各层都已合并回最外层，cur就是完整答案。
解题步骤
- 创建次数栈、前缀栈，初始化空的
cur和count = 0。- 遇到数字，将它累积到
count，支持多位重复次数。- 遇到
[，把次数与外层前缀分别入栈，清零次数，并创建新的当前层缓冲区。- 遇到普通字母，追加到当前层结果。
- 遇到
]，从两栈各弹出一项，将当前结果重复指定次数并追加到外层前缀，再恢复为新的cur。- 扫描完输入，返回
cur对应的字符串。
代码实现
class Solution {
public String decodeString(String s) {
Deque<Integer> counts = new ArrayDeque<>();
Deque<StringBuilder> prefixes = new ArrayDeque<>();
StringBuilder cur = new StringBuilder();
int count = 0;
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (Character.isDigit(ch)) {
count = count * 10 + ch - '0';
} else if (ch == '[') {
counts.push(count);
// 同时保存外层前缀和次数，新层使用独立缓冲。
prefixes.push(cur);
count = 0;
cur = new StringBuilder();
} else if (ch == ']') {
int repeat = counts.pop();
StringBuilder prev = prefixes.pop();
for (int j = 0; j < repeat; j++) {
// 把内层结果按次数追加到外层前缀之后。
prev.append(cur);
}
cur = prev;
} else {
cur.append(ch);
}
}
return cur.toString();
}
}
func decodeString(s string) string {
counts := make([]int, 0)
prefixes := make([][]byte, 0)
cur := make([]byte, 0)
count := 0
for i := 0; i < len(s); i++ {
ch := s[i]
if ch >= '0' && ch <= '9' {
count = count*10 + int(ch-'0')
} else if ch == '[' {
counts = append(counts, count)
// 同时保存外层前缀和次数，新层使用独立缓冲。
prefixes = append(prefixes, cur)
count = 0
cur = make([]byte, 0)
} else if ch == ']' {
repeat := counts[len(counts)-1]
counts = counts[:len(counts)-1]
prev := prefixes[len(prefixes)-1]
prefixes = prefixes[:len(prefixes)-1]
for j := 0; j < repeat; j++ {
// 把内层结果按次数追加到外层前缀之后。
prev = append(prev, cur...)
}
cur = prev
} else {
cur = append(cur, ch)
}
}
return string(cur)
}
复杂度分析
设输入长度为
n，最大嵌套深度为d，解码后的长度为L。
- 时间复杂度：$O(n + dL)$。扫描输入需要 $O(n)$，字符串展开还需要复制字符；同一个最终字符在逐层合并时最多被复制
d次，不能只按输入长度计算。- 空间复杂度：$O(L + d)$。两个栈最多保存
d层信息，各层前缀、当前内容及最终结果占用与解码长度同阶的空间。
关键点总结
[!green]
cur只表示当前层已完成的内容，尚未恢复的外层状态由栈保存。- 两个栈同步入栈和出栈，同一层的重复次数必须与它的外层前缀对应。
- 关闭一层时，顺序始终是“外层前缀 + 内层结果重复若干次”，只有内层结果参与重复。
易错点总结
[!yellow]
- 用当前数字覆盖
count，只能解析一位数；新数字到来时要先把已有数值乘10。- 进入新层后不清零
count，后续次数会混入前一层的数值。- 只保存重复次数、不保存外层前缀，会丢失进入括号之前已经解析的内容。
- 把整个“外层前缀 + 内层结果”一起重复，会错误地放大本来位于括号外的内容。
- 新层必须使用独立缓冲区。Java 清空已入栈的同一个
StringBuilder，或 Go 用cur = cur[:0]复用底层数组，都可能破坏保存的外层前缀。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 385. 迷你语法分析器 | 中等 | 同样解析嵌套括号，本题把子串重复展开，原题构造嵌套整数节点。 |
| 726. 原子的数量 | 困难 | 同样用栈或递归处理分层文本，原题按括号外系数汇总原子次数。 |
| 224. 基本计算器 | 困难 | 用栈保存嵌套表达式的中间状态；本题展开带重复次数的嵌套片段，该题处理带括号的加减表达式。 |
| 227. 基本计算器 II | 中等 | 用栈保存嵌套表达式的中间状态；本题展开带重复次数的嵌套片段，该题优先结算乘除再合并加减。 |
| 772. 基本计算器 III | 困难 | 用栈保存嵌套表达式的中间状态；本题展开带重复次数的嵌套片段，该题同时处理括号与运算优先级。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！