0394. 字符串解码 #
- 标签:栈、深度优先搜索
- 难度:中等
题目大意 #
描述:给定一个经过编码的字符串 s
。
要求:返回 s
经过解码之后的字符串。
说明:
- 编码规则:
k[encoded_string]
。encoded_string
为字符串,k
为整数。表示字符串encoded_string
重复k
次。 - $1 \le s.length \le 30$。
s
由小写英文字母、数字和方括号[]
组成。s
保证是一个有效的输入。s
中所有整数的取值范围为 $[1, 300]$。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:栈 #
- 使用两个栈
stack1
、stack2
。stack1
用来保存左括号前已经解码的字符串,stack2
用来存储左括号前的数字。 - 用
res
存储待解码的字符串、num
存储当前数字。 - 遍历字符串。
- 如果遇到数字,则累加数字到
num
。 - 如果遇到左括号,将当前待解码字符串入栈
stack1
,当前数字入栈stack2
,然后将res
、nums
清空。 - 如果遇到右括号,则从
stack1
的取出待解码字符串res
,从stack2
中取出当前数字num
,将其解码拼合成字符串赋值给res
。 - 如果遇到其他情况(遇到字母),则将当前字母加入
res
中。
- 如果遇到数字,则累加数字到
- 遍历完输出解码之后的字符串
res
。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(n)$。