LC394　字符串解码¶

中等通过率 61.8%python3核心代码模式栈样例通过牛客 AC栈递归字符串

牛客原题　源码

讲解章节：栈

一句话

用栈保存「进入方括号前的半成品和重复次数」，出括号时回填。

解题思路¶

这题考什么¶

编码规则 k[内容] 可以任意嵌套，如 3[a2[c]]。嵌套结构意味着处理到内层时外层还没算完，必须把外层的未完成状态先存起来——这正是栈的用途，也是「递归下降解析」用迭代方式写出来的样子。见栈。

维护两个东西：cur 是「当前这层已经拼好的字符串」，栈里存二元组 (进入本层之前外层的 cur, 本层要重复的次数)。四类字符各司其职：

数字   累积成重复次数 num（可能是多位数）
'['    把 (cur, num) 压栈，然后把 cur 与 num 清空，开始拼内层
']'    本层拼完了：弹出 (prev, k)，令 cur = prev + cur * k
字母   直接追加到 cur

关键在于 '[' 那一步同时保存两样东西：外层已经拼到一半的串 prev，以及这一层的重复次数 k。只存其中一个都不够——只存次数，出括号时不知道该接在哪个前缀后面；只存前缀，则不知道要重复几次。

出括号时的 prev + cur * k 顺序不能颠倒：cur 是括号内部的内容，要先自我重复 k 次，再整体接到外层前缀 prev 的后面。

数据规模与复杂度¶

1 <= s.length <= 30，重复次数 k 在 [1, 300]，题面保证输出长度不超过 1e5。时间与空间都是 O(输出长度) 级：每个输出字符最终被拼接一次，栈深等于括号嵌套层数，最坏也不过 s 的长度。朴素做法「反复用正则找最内层的 k[...] 展开，直到没有方括号」也能做对，但每轮都要重建整个字符串，嵌套深时是平方级的重复拷贝。

坑在哪¶

重复次数可能是多位数。题面允许 k 到 300，"100[a]" 里的 1、0、0 必须累积成 100，写法是 num = num * 10 + int(ch)。只取一位就会把 100[a] 解成 1 个 a 再多出两段乱码。
压栈之后必须把 num 与 cur 一起清零。num 不清零，下一个括号会继承上一层的次数；cur 不清零，内层会把外层已拼好的内容一起重复一遍——3[a2[c]] 会错成把 "a" 也乘进内层。
栈里存的是二元组，不是单个值。分成两个栈也可以，但必须成对进出；只压一个的写法在嵌套时必然丢信息。
出括号时的拼接顺序是 prev + cur * k。写成 (prev + cur) * k 会把外层前缀也重复 k 次，2[abc]3[cd]ef 会当场算错。
题面保证输入合法（括号配对、数字只表示次数、不出现 3a 或 2[4]），所以不需要处理非法输入；但 '['、']' 与数字的分支判断顺序仍要写全，漏掉任何一类会静默地把字符当字母追加进结果。
用 str 直接累加 cur 在本题的规模下没问题（输出上限 1e5），若规模再大几个量级，才需要改成 list 收集片段最后 join。
严格比对：解码结果唯一，没有多解。

样例复核¶

s = "3[a2[c]]"，期望 "accaccacc"。

'3'  num = 3
'['  压 ("", 3)，cur = ""，num = 0
'a'  cur = "a"
'2'  num = 2
'['  压 ("a", 2)，cur = ""，num = 0
'c'  cur = "c"
']'  弹 ("a", 2)，cur = "a" + "c" * 2 = "acc"
']'  弹 ("", 3)，cur = "" + "acc" * 3 = "accaccacc"

输出 "accaccacc"，与题面一致。第二次压栈存的前缀是 "a"，正说明「进入内层前外层的半成品」必须单独保存——否则 "a" 会被乘进内层。

参考实现¶

solutions/leetcode/LC394/sol.py
from typing import List, Optional


class Solution:
    def decodeString(self, s: str) -> str:
        # 栈里存二元组（进入本层之前外层已拼好的串, 本层的重复次数）。
        # 两样都要存：只存次数不知道该接到哪个前缀后面，只存前缀不知道重复几次
        stack = []
        # cur 是「当前这一层已经拼好的内容」，num 是正在累积的重复次数
        cur = ""
        num = 0
        for ch in s:
            if ch.isdigit():
                # 次数可能是多位数（题面允许到 300），逐位累积成十进制整数。
                # 只取一位会把 100[a] 解成 1 个 a 加两段乱码
                num = num * 10 + int(ch)
            elif ch == "[":
                # 进入新的一层：把外层的半成品和这一层的次数一起封存，
                # 然后 cur 与 num 都要清零——cur 不清零，内层会把外层内容也重复一遍；
                # num 不清零，下一个括号会继承上一层的次数
                stack.append((cur, num))
                cur = ""
                num = 0
            elif ch == "]":
                # 本层结束：括号内部的 cur 先自我重复 k 次，再接到外层前缀之后。
                # 写成 (prev + cur) * k 会把外层前缀也一起重复，结果错
                prev, k = stack.pop()
                cur = prev + cur * k
            else:
                # 普通字母，直接并入当前层
                cur += ch
        # 扫完时所有括号都已配平（题面保证输入合法），cur 就是最外层的完整结果
        return cur

LC394 字符串解码¶