394. 字符串解码

题目链接（中等）

题目描述

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为：k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k，例如不会出现像 3a 或 2[4] 的输入。

测试用例保证输出的长度不会超过 10^5。

数据范围：

1 <= s.length <= 30
s 由小写英文字母、数字和方括号 [] 组成
s 保证是一个有效的输入
s 中所有整数的取值范围为 [1, 300]

示例

示例 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"

核心思路

字符串可能嵌套，例如 3[a2[c]]，需要从内到外逐层解码：

先解析 2[c] → "cc"；
再解析 3[acc] → "accaccacc"。

难点在于嵌套结构，两种处理思路：

栈：用栈保存「进入括号前」的状态（数字和已解析的字符串），遇到 ] 就出栈合并；
递归：遇到 k[...] 就递归解析括号内的字符串，返回后乘以 k，继续处理后面的内容。

两种方法的本质相同，都是括号匹配的思想。

方法一：栈（保存数字 + 字符串）

思路及解法

用一个栈保存元组 (prev_res, k)：

prev_res：进入当前括号前已解析的字符串；
k：当前括号对应的重复次数。

同时用两个变量：

res：当前正在构建的字符串；
k：当前累计的重复次数（可能是多位数）。

遍历规则：

数字：累积计算 k = k * 10 + int(ch)（处理多位数）；
[：把 (res, k) 压入栈，然后重置 res = ""、k = 0，准备解析括号内部；
]：弹出 (prev_res, repeat)，令 res = prev_res + res * repeat，把当前括号的内容重复并拼接到前缀后面；
字母：直接追加到 res。

举例：s = "3[a2[c]]"

步骤	遇到	栈	`res`	`k`
1	`3`	`[]`	`""`	3
2	`[`	`[("", 3)]`	`""`	0
3	`a`	`[("", 3)]`	`"a"`	0
4	`2`	`[("", 3)]`	`"a"`	2
5	`[`	`[("", 3), ("a", 2)]`	`""`	0
6	`c`	`[("", 3), ("a", 2)]`	`"c"`	0
7	`]`	`[("", 3)]`	`"acc"`	0
8	`]`	`[]`	`"accaccacc"`	0

最终返回 "accaccacc"。

代码

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        res = ""
        k = 0

        for ch in s:
            if ch.isdigit():
                k = k * 10 + int(ch)
            elif ch == '[':
                stack.append((res, k))
                res = ""
                k = 0
            elif ch == ']':
                prev_res, repeat = stack.pop()
                res = prev_res + res * repeat
            else:
                res += ch

        return res

复杂度分析

时间复杂度： $O(L)$ ， $L$ 是解码后字符串的长度。每个字符处理一次，字符串拼接总量与输出长度成正比。
空间复杂度： $O(L)$ ，栈和结果字符串所需空间。

方法二：递归

思路及解法

把字符串视为一种「嵌套结构」，可以用递归解析：

递归函数 dfs()：从当前位置 i 开始解析，遇到 ] 或字符串末尾就返回。

解析规则：

若当前字符是数字：
- 解析出完整的数字 k；
- 跳过 [；
- 递归解析括号内的内容 inner；
- 跳过 ]；
- 返回 inner * k，继续处理后面的内容；
若当前字符是字母：
- 取一个字符，继续解析后面的内容；
若当前字符是 ] 或到达末尾：
- 返回空字符串（终止条件）。

关键点：用一个外部指针 i（nonlocal）跟踪当前位置，递归时共享。

代码

class Solution:
    def decodeString(self, s: str) -> str:
        n = len(s)
        i = 0

        def dfs() -> str:
            nonlocal i
            res = ""
            while i < n and s[i] != ']':
                if s[i].isdigit():
                    # 解析数字
                    k = 0
                    while i < n and s[i].isdigit():
                        k = k * 10 + int(s[i])
                        i += 1
                    # 跳过 '['
                    i += 1
                    # 递归解析括号内部
                    inner = dfs()
                    # 跳过 ']'
                    i += 1
                    res += inner * k
                else:
                    # 字母，直接追加
                    res += s[i]
                    i += 1
            return res

        return dfs()

复杂度分析

时间复杂度： $O(L)$ ，每个字符处理一次。
空间复杂度： $O(L)$ ，递归栈深度最坏为嵌套层数，最坏情况可能达到 $O(|s|)$ 。

两种方法对比

方法	时间	空间	特点
栈	$O(L)$	$O(L)$	思路直观，一个栈存元组 `(字符串, 数字)`
递归	$O(L)$	$O(L)$	代码更短，但需要理解指针共享

关键细节

1. 为什么用 `(res, k)` 元组入栈

每次遇到 [，都需要保存两个状态：

进入括号前已经解析好的字符串 prev_res；
当前括号对应的重复次数 k。

两者是一一对应的，用一个元组一起入栈最自然。相比两个独立栈，代码更紧凑。

2. 数字可能有多位

题目中 k 的范围是 [1, 300]，最多三位。必须用 k = k * 10 + int(ch) 逐位累积，不能只读一位。

3. 遇到 `]` 时的合并操作

res = prev_res + res * repeat

res * repeat：把括号内的内容重复 repeat 次；
prev_res：括号之前已经解析好的前缀；
结果作为新的 res，继续和外层合并。

4. 递归法中的终止条件

while i < n and s[i] != ']'：

遇到 ] 说明当前层结束，返回 res；
到达末尾 i == n 也返回，避免越界。

外层调用 dfs 后要 i += 1 跳过 ]，否则会死循环。

5. 与括号匹配问题的联系

字符串解码本质上是一个括号匹配 + 状态栈问题。类似的问题还有：

有效的括号（LC 20）；
基本计算器（LC 224/227）；
逆波兰表达式求值（LC 150）。

它们的共同思路都是「遇到左括号入栈，右括号出栈计算」。

总结

本质：括号嵌套结构，需要从内到外解析；
栈方法：
- 栈里存 (进入括号前的字符串, 重复次数)；
- 遇到 [ 入栈并重置，遇到 ] 出栈合并；
- res = prev_res + res * repeat；
递归方法：
- 用 dfs() 解析当前层，遇到 ] 或末尾返回；
- 遇到数字读 k，跳 [，递归，跳 ]，返回 inner * k；
复杂度：两种方法都是 $O(L)$ 时间、 $O(L)$ 空间；
通用套路：「嵌套括号」类问题 → 栈或递归。

394. 字符串解码

394. 字符串解码

题目描述

示例

核心思路

方法一：栈（保存数字 + 字符串）

思路及解法

代码

复杂度分析

方法二：递归

思路及解法

代码

复杂度分析

两种方法对比

关键细节

1. 为什么用 (res, k) 元组入栈

2. 数字可能有多位

3. 遇到 ] 时的合并操作

4. 递归法中的终止条件

5. 与括号匹配问题的联系

总结

相关题目

1. 为什么用 `(res, k)` 元组入栈

3. 遇到 `]` 时的合并操作