0394. 字符串解码 #
- 标签:栈、深度优先搜索
- 难度:中等
题目大意 #
给定一个经过编码的字符串 s
。
要求:返回 s
经过解码之后的字符串。
- 编码规则:
k[encoded_string]
。encoded_string
为字符串,k
为整数。表示字符串encoded_string
重复k
次。
解题思路 #
使用两个栈 stack1
、stack2
。stack1
用来保存左括号前已经解码的字符串,stack2
用来存储左括号前的数字。再用 res
存储待解码的字符串、num
存储当前数字。然后遍历字符串。
- 如果遇到数字,则累加数字到
num
。 - 如果遇到左括号,将当前待解码字符串入栈
stack1
,当前数字入栈stack2
,然后将res
、nums
清空。 - 如果遇到右括号,则从
stack1
的取出待解码字符串res
,从stack2
中取出当前数字num
,将其解码拼合成字符串赋值给res
。 - 如果遇到其他情况(遇到字母),则将当前字母加入
res
中。
代码 #
|
|