- 标签:栈、递归、字符串
- 难度:中等
描述:给定一个经过编码的字符串 s
。
要求:返回 s
经过解码之后的字符串。
说明:
- 编码规则:
k[encoded_string]
。encoded_string
为字符串,k
为整数。表示字符串encoded_string
重复k
次。 -
$1 \le s.length \le 30$ 。 -
s
由小写英文字母、数字和方括号[]
组成。 -
s
保证是一个有效的输入。 -
s
中所有整数的取值范围为$[1, 300]$ 。
示例:
- 示例 1:
输入:s = "3[a]2[bc]"
输出:"aaabcbc"
- 示例 2:
输入:s = "3[a2[c]]"
输出:"accaccacc"
- 使用两个栈
stack1
、stack2
。stack1
用来保存左括号前已经解码的字符串,stack2
用来存储左括号前的数字。 - 用
res
存储待解码的字符串、num
存储当前数字。 - 遍历字符串。
- 如果遇到数字,则累加数字到
num
。 - 如果遇到左括号,将当前待解码字符串入栈
stack1
,当前数字入栈stack2
,然后将res
、nums
清空。 - 如果遇到右括号,则从
stack1
的取出待解码字符串res
,从stack2
中取出当前数字num
,将其解码拼合成字符串赋值给res
。 - 如果遇到其他情况(遇到字母),则将当前字母加入
res
中。
- 如果遇到数字,则累加数字到
- 遍历完输出解码之后的字符串
res
。
class Solution:
def decodeString(self, s: str) -> str:
stack1 = []
stack2 = []
num = 0
res = ""
for ch in s:
if ch.isdigit():
num = num * 10 + int(ch)
elif ch == '[':
stack1.append(res)
stack2.append(num)
res = ""
num = 0
elif ch == ']':
cur_res = stack1.pop()
cur_num = stack2.pop()
res = cur_res + res * cur_num
else:
res += ch
return res
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(n)$。