Leetcode Link: 394. 字符串解码 - 力扣（LeetCode）
题目
给定一个经过编码的字符串，返回它解码后的字符串
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
解法一
思路：自己思路
显然这是一个递归问题，每次拿到一个新的字符串，都可以送进这个递归函数中，不断递归。
这道题主要是 1) 有点绕，2) 有点乱, 3) 细节有点多
仔细观察字符串的形式，大致思路如下
- 我们假定每次输入的字符串是不含两边的
'['和']' - 当输入的字符串中不含方括号时，说明当前的字符串就是最内部的字符串，直接返回重复times次的该字符串即可
- 若含有括号，则遍历字符串先看看遇到的是数字还是字母，如果是字母，则直接可以添加到当前的解码字符串中，反之说明是下一个内部字符串出现的次数。（注意这个次数可能>9，即可能占多位）
- 若遇到了方括号，则利用栈来判定接下来的哪些字符串是内部字符串，当栈空时，直接送入下一层递归中。但是注意初始化
next_time和next_strs - 最后记得把当前函数解码出来的字符串重复 times 次后返回
题解：
class Solution:
def decodeString(self, s: str) -> str:
def process(times, strs):
# 递归终止条件：遇到 plain string
if '[' not in strs:
lst = [strs] * times
return ''.join(lst)
cur = '' # 当前字符串
bucket = [] # [ 和 ] 的栈
next_strs = '' # 下一个string
next_time = '' # 下一个string出现的次数
for i in range(len(strs)):
# 如果栈空，则只可能是plain string或者下一个string的出现次数
if len(bucket) == 0:
if strs[i].isalpha():
cur = cur + strs[i]
elif strs[i].isnumeric():
next_time = next_time + strs[i]
# 处理遇到的方括号， 必需注意第二个if的位置，改变位置会报错。
if strs[i] == ']':
bucket.pop()
if len(bucket) > 0: # 如果弹出之后栈里还有，说明当前的str还是next_str的一部分
next_strs = next_strs + strs[i]
if strs[i] == '[':
# 遇到了右括号，说明肯定已经开始了找next_str，这一句会多次执行，但不影响结果
next_time = int(next_time)
bucket.append(1)
# 栈空同时next_strs不为空，说明已经找完了next_str，送去处理。
if next_strs != '' and len(bucket) == 0:
cur = cur + process(next_time, next_strs)
next_strs = '' #这两个必需重置
next_time = ''
cur = [cur]*times #别忘了当前的字符串也要重复出现times次
return ''.join(cur)
return process(1, s)
解法二
思路：题解
只用栈
- 本题核心思路是在栈里面每次存储两个信息, (左括号前的字符串, 左括号前的数字), 比如
abc3[def], 当遇到第一个左括号的时候，压入栈中的是("abc", 3), 然后遍历括号里面的字符串def, 当遇到右括号的时候, 从栈里面弹出一个元素(s1, n1), 得到新的字符串为s1+n1*"def", 也就是abcdefdefdef。对于括号里面嵌套的情况也是同样处理方式。 - 凡是遇到左括号就进行压栈处理，遇到右括号就弹出栈，栈中记录的元素很重要。
题解：
class Solution:
def decodeString(self, s: str) -> str:
stack = [] # (str, int) 记录左括号之前的字符串和左括号外的上一个数字
times = 0
res = "" # 实时记录当前可以提取出来的字符串
for c in s:
if c.isdigit():
times = times * 10 + int(c)
elif c == "[":
stack.append((res, times))
res, times = "", 0
elif c == "]":
cur = stack.pop()
res = cur[0] + res * cur[1]
else:
res += c
return res解法三
思路：
题解：