LeetCode 394. 字符串解码

2026-08-20 HGNULB 约 5 分钟

文章信息 19 个分类 3 个标签

分类

LeetCode CodeTop 中等已解决 100-200 字节跳动微软美团阿里巴巴腾讯猿辅导百度滴滴华为拼多多虾皮小红书 LeetCode 75 LeetCode 热题 100

题目描述

✅ 394. 字符串解码

题意分析

输入是一段编码字符串，规则是 k[encoded_string] 表示把方括号里的内容原样重复 k 次，要求返回完全解码后的字符串。

题面保证输入是有效的：方括号成对且正确嵌套，重复次数是正整数，并且原始待重复的内容里不含数字。这条保证很关键——它意味着扫描时不需要做任何语法校验，只要看见数字就一定是在读某个方括号的重复次数，看见 [ 就一定是进入新的一层。

结构可以嵌套，例如外层重复次数要等到内层解码完成后才能派上用场。所以「当前正在拼装的字符串」不止一个，而是一叠：每往里进一层，外层那个半成品都必须原封不动地保存下来，等内层做完再回填。

重复次数可能是多位数，读数字时必须连续累积而不能只取一位。

边界情形有四类：整个串没有任何方括号，答案就是原串；同一层出现多段方括号，后一段解码完要接在前一段之后；方括号前面已经有拼好的字母，回填时不能丢掉这段前缀；解码结果的长度可以远远超过输入长度。

解法：双栈解析嵌套表达式

核心思路

扫描字符串时，用 cur 保存当前层结果、count 保存当前重复次数。遇到 [ 时把外层前缀和次数分别压栈并开始新一层；遇到 ] 时弹出上下文，将当前层重复后接回外层前缀。栈的后进先出顺序正好对应括号的嵌套关系。

解题步骤

遇到数字，用 count = count * 10 + digit 读取完整的多位数。

遇到 [，保存 count 和 cur，然后清空当前状态。

遇到字母，直接追加到 cur。

遇到 ]，弹出重复次数和外层前缀，拼成新的 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)
}

复杂度分析

时间复杂度：最坏为 $O(n + dL)$，n 为输入长度，d 为最大嵌套深度，L 为解码后长度；字符在回填外层时最多被复制 d 次。

空间复杂度：$O(L + d)$，用于各层字符串、计数栈和返回结果。

关键点总结

多位重复次数必须按十进制逐位累积。

进入新层前要同时保存外层前缀和重复次数。

结束一层时的拼接顺序是“外层前缀 + 重复后的当前层”。

易错点总结

[ 后未清零 count，会影响下一段重复次数。

只保存次数而未保存外层前缀，会丢失括号前已经解析的内容。

] 时把当前层放到外层前缀之前，会颠倒字符串顺序。

Go 中用 cur = cur[:0] 开启新层会复用底层数组，可能覆盖已入栈的前缀。

相似题目

题目	难度	考察点
20. 有效的括号	简单	只判断配对合法性，栈里存的是待匹配的括号本身，不需要携带任何上下文
150. 逆波兰表达式求值	中等	输入已是后缀形式，栈里存的是运算数，完全没有「挂起再回填」的动作
224. 基本计算器	困难	挂起的上下文是「已累加结果与当前符号」，还要单独处理一元负号，转移类别比本题多
227. 基本计算器 II	中等	没有括号但有运算符优先级，用「延迟入栈」代替嵌套上下文
385. 迷你语法分析器	中等	同为嵌套解析，但要构造嵌套的对象树而不是拼接字符串，回填的是子结构引用
726. 原子的数量	困难	挂起的上下文是一张元素计数表，回填时要按倍数合并整张表，最后还要排序输出
856. 括号的分数	中等	挂起的是一个分数而不是字符串，只用一个栈即可，最能对照出「上下文该存几样」
1096. 花括号展开 II	困难	嵌套里同时有并集与连接两种运算，结果需去重排序，是本题的集合版本