394. Decode String

Loading...LeetCode

因为会有括号的嵌套，直接遍历分情况处理的话无法搞定。看作一种DFS来遍历会比较方便，遇到起始括号就是往下search，遇到结束括号是结束当前 subtree、往上返回。

感觉stack才是DFS的精髓，但是tree based 题目很多都用不上stack...

class Solution:
    def decodeString(self, s: str) -> str:
        stack = collections.deque()
        number, cur = 0, ''
        for c in s:
            if c == '[':
                # push当前层的记录，然后初始化记录开始下一层
                stack.append((cur, number))
                number, cur = 0, ''
            elif c == ']':
                # 
                saved, repeat = stack.pop()
                cur = saved + repeat*cur
            elif c.isdigit():
                # 处理超过1位的数字
                number = number*10 + int(c)
            else:
                cur += c
        return cur