394. 字符串解码
https://leetcode-cn.com/problems/decode-string/
前言: 一开始拿到题时, 是先用最直接的想法做的.大致思路是: 遍历字符串, 每次遇到 [ 记录下位置,遇到 ]记录下位置.遍历完成后, 用切片的方式,获取字符串中括号之间的内容。实际做的过程中, 遇到了这个用例: s = "3[a2[c]]".然后迫不得已得写很多if 和 else, 最后把自己绕进去了. 最终放弃了这个思路,参考题解中大佬的思路.
正确思路: 1. 使用栈的思路, 遍历字符串,遇到非']'就入栈, 遇到就 '[' 就出栈.遇到数字时,先循环下尝试获取所有的数字,因为可能出现类似100[abc]这样的情况。
2.每次循环完并"解码"后, 将解码后的字符串继续添加到栈中。这样每次循环时,都会在这个栈中继续操作.有一点类似于"递归"
class Solution:
def decodeString(self, s: str) -> str:
stack = []
for c in s:
if c == ']':
repeatStr = ''
repeatCount = ''
while stack and stack[-1] != '[':
repeatStr = stack.pop() + repeatStr
stack.pop() # pop 掉 "["
while stack and stack[-1].isdigit():
repeatCount = stack.pop() + repeatCount
stack.append(repeatStr * int(repeatCount))
else:
stack.append(c)
return "".join(stack)
遇到类似括号的问题时, 可以想栈的操作来fix. 相似的题有20. 有效的括号