给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
同时，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
用两个栈来分别存储数字和字符串，遇到数字就更新数字，遇到左括号就将数字和左括号分别入栈，遇到右括号就将栈顶的字符串出栈，直到遇到左括号，然后将字符串翻转后重复数字次入栈。最后将栈中的字符串拼接起来即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution:
def decodeString(self, s: str) -> str:
num_stack, str_stack = [], []
cur_num = 0
for st in s:
if st.isdigit():
print(cur_num)
cur_num = cur_num*10 + int(st)
elif st == '[':
num_stack.append(cur_num)
cur_num = 0
str_stack.append(st)
elif not st == ']':
str_stack.append(st)
else:
tmp_str = ''
top = str_stack.pop()
while top != '[':
tmp_str += top
top = str_stack.pop()
tmp_str = tmp_str[::-1]*int(num_stack.pop())
for tmp in tmp_str:
str_stack.append(tmp)
return ''.join(str_stack)
|