| 题目链接 | 394. 字符串解码 |
|---|---|
| 思路 | 字符串模拟；出现相同子问题，可以使用递归或者栈解决 |
| 题解链接 | 字符串解码（辅助栈法 / 递归法，清晰图解） |
| 关键点 | 栈：需要存储（重复次数，当前字符串）；递归：需要范围 内嵌字符串及结束位置 |
| 时间复杂度 | \(O(n)\) |
| 空间复杂度 | \(O(n)\) |
代码实现（栈）：
class Solution:
def decodeString(self, s: str) -> str:
stk = []
num = 0
answer = ""
for ch in s:
if ch.isdigit():
num = num * 10 + int(ch)
elif ch == "[":
stk.append((answer, num))
answer, num = "", 0
elif ch == "]":
prev_str, cur_times = stk.pop()
answer = prev_str + cur_times * answer
else:
answer += ch
return answer
代码实现（递归）：
class Solution:
def decodeString(self, s: str) -> str:
def decode(i):
answer, n = "", 0
while i < len(s):
if s[i].isdigit():
n = n * 10 + int(s[i])
elif s[i] == '[':
i, nested = decode(i+1)
answer += n * nested
n = 0
elif s[i] == ']':
return i, answer
else:
answer += s[i]
i += 1
return answer
return decode(0)