思路
两个栈，一个字母栈，一个数字栈
左括号开始就进入字母栈，右括号就开始出栈(出栈生成的结果要重新入字母栈)，括号也要进栈，标志边界
# a：3 2 -> a：3 -> a：
# b：[ a [ c ] -> b：[ a c c ] -> b：a c c a c c a c c
# res: a c c a c c a c c
# a：3 -> a：2 -> a：
# b：[ a ] -> b：a a a [ b c ] -> b：a a a b c b c
# res:
代码
class Solution:
def decodeString(self, s: str) -> str:
'''
case: "100[leetcode]"
'''
stack_num = []
stack_alpha = []
flag = False
for i in range(len(s)):
cur = s[i]
if cur.isdigit():
if flag is False:
stack_num.append(int(cur))
else:
pre = int(stack_num.pop())
num = pre * 10 + int(cur)
stack_num.append(num)
flag = True
elif cur == ']':
flag = False
word = ''
while len(stack_alpha) > 0:
tmp = stack_alpha.pop()
if tmp == '[':
break
word += tmp
# 逆序退出栈
count = int(stack_num.pop())
while count > 0:
# for ele in word:
for j in range(len(word) - 1, -1, -1):
stack_alpha.append(word[j])
count -= 1
else:
flag = False
stack_alpha.append(cur)
if len(stack_num) != 0:
return ''
return ''.join(stack_alpha)
复杂度
时间复杂度：o(n)
空间复杂度：o(n)
