394. 字符串解码 (Medium)
专题归类： 06-栈与堆 LeetCode 链接： https://leetcode.cn/problems/decode-string/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为：k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k，例如不会出现像 3a 或 2[4] 的输入。
示例 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"
题目详细分析
- 数据范围： 1 ≤ s.length ≤ 30，但解码后的字符串长度可能远大于原始输入（因为重复展开）。最大长度可能非常大（指数级），但题目中 k 范围应该有限。
- 输入输出特征： 输入只包含字母、数字和
[]。数字只出现在[之前，表示重复次数。字母可以是小写或大写？题目说字母，实际是小写英文字母。 - 边界条件：
- 无嵌套：
3[a]最简单。 - 嵌套多层：
3[a2[c]b]（a 后面嵌套了 2[c]）。 - 数字可能多位：
10[a]表示 “a” 重复 10 次。 - 数字可能为 1：
1[a]→ “a”，等价于无编码。 - 开头或结尾有无编码的字母：
abc3[d]ef。
- 无嵌套：
- 核心约束： 嵌套结构是核心难点，需要后遇到的
[...]先解码（LIFO 特性），因此使用栈来解决。 - 隐藏条件： 括号内的内容可能既包含字母也包含嵌套的
k[...]。解码时要从最内层开始向外处理。
小白版直白理解
就像在做 俄罗斯套娃：一层套一层，每层都有个数字告诉你这层娃娃要复制几份。
最里层的 2[c] 表示 “cc”，往外一层 3[a + 里层结果] = 3[acc] = “accaccacc”。
从里到外的顺序正好和栈的 后进先出 一致：最里层的 ] 最先遇到，但我们需要先处理它。
想象你在剥洋葱：
- 看到
[时，把当前已经处理的字符串和数字存起来，然后清零开始处理内层 - 看到
]时，把内层结果弹出来，乘以数字，拼接到上一层的结果后面
解题思路
思路一：辅助栈法（推荐）
核心思想： 用两个变量 cur_str 和 cur_num 分别追踪当前正在构建的字符串和当前累积的数字。遇到 [ 时，将当前状态入栈并重置；遇到 ] 时，从栈中弹出状态并拼接结果。
def decodeString(s):
stack = [] # 存储 (之前的字符串, 重复次数)
cur_str = '' # 当前正在构建的字符串
cur_num = 0 # 当前累积的数字
for ch in s:
if ch.isdigit():
cur_num = cur_num * 10 + int(ch) # 处理多位数
elif ch == '[':
stack.append((cur_str, cur_num)) # 保存当前状态
cur_str = '' # 重置，开始处理内层
cur_num = 0 # 重置数字
elif ch == ']':
prev_str, num = stack.pop() # 取出外层状态
cur_str = prev_str + cur_str * num # 拼接：外层 + 内层×次数
else: # 字母
cur_str += ch
return cur_str复杂度： 时间 O(n)（n 为解码后字符串长度），空间 O(n)
思路二：双栈法（数字栈 + 字符串栈）
将数字和字符串分别存储在独立的栈中，逻辑更清晰但代码稍长。
def decodeString(s):
num_stack = [] # 数字栈
str_stack = [] # 字符串栈
cur_num = 0
cur_str = ''
for ch in s:
if ch.isdigit():
cur_num = cur_num * 10 + int(ch)
elif ch == '[':
num_stack.append(cur_num)
str_stack.append(cur_str)
cur_num = 0
cur_str = ''
elif ch == ']':
cur_str = str_stack.pop() + cur_str * num_stack.pop()
else:
cur_str += ch
return cur_str思路三：递归解法
k[...] 具有递归结构：一个编码字符串可以递归地解码。遇到 [ 时递归进入内层，遇到 ] 时返回结果。
def decodeString(s):
def dfs(i):
res = ''
num = 0
while i < len(s):
if s[i].isdigit():
num = num * 10 + int(s[i])
elif s[i] == '[':
inner_str, i = dfs(i + 1) # 递归处理内层
res += inner_str * num
num = 0
elif s[i] == ']':
return res, i
else: # 字母
res += s[i]
i += 1
return res, i
result, _ = dfs(0)
return result复杂度： 时间 O(n)，空间 O(n)（递归栈深度等于嵌套层数）
易错点
- 多位数处理： 数字可能不止一位（如
12[a]），需要用cur_num = cur_num * 10 + int(ch)累积，而不是直接赋值。忘记处理多位数是最常见的 bug。 - 嵌套重置： 遇到
[时需要重置cur_str和cur_num，否则内层会错误地继承外层的状态。 - 拼接顺序：
prev_str + cur_str * num— 外层的字符串应该在前，内层重复后的字符串在后。顺序搞反会导致结果错误（如3[a2[c]]会得到 “ca” × 3 而不是 “acc” × 3）。 - 栈的初始化： 一开始栈是空的，遇到数字后累积，直到
[才入栈。注意栈中的状态是 入栈时的值，不是出栈时再计算的。 - 字符串末尾无括号： 如
abc3[cd]xyz，最后的 “xyz” 直接拼接到结果即可。
框架提炼
编码字符串解码模板（栈处理嵌套）：
def decode_nested_string(s):
"""通用模板：处理 k[pattern] 嵌套解码"""
stack = []
cur_str = ''
cur_num = 0
for ch in s:
if ch.isdigit():
cur_num = cur_num * 10 + int(ch)
elif ch == '[':
stack.append((cur_str, cur_num))
cur_str = ''
cur_num = 0
elif ch == ']':
prev_str, num = stack.pop()
cur_str = prev_str + cur_str * num
else:
cur_str += ch
return cur_str这种「遇到分隔符入栈/出栈」的模式还可以解决：
- 表达式求值（遇到
)出栈计算） - HTML 标签解析（遇到
</tag>出栈检查） - JSON 解析器