394 Decode String

https://leetcode.com/problems/decode-string/description/

solution

• 栈

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        cur_num = 0
        cur_str = ''

        for char in s:
            if char == '[':
                stack.append(cur_str)  # 栈也可以直接保存元素 (cur_str, cur_num), 思路关键是字母和次数都分别进栈, 方便重新开始统计
                stack.append(cur_num)
                cur_str = ''
                cur_num = 0
            elif char == ']':
                prev_num = stack.pop()  # 注意这里两个pop出来的都要用新的名字
                prev_str = stack.pop()
                cur_str = prev_str + prev_num * cur_str  # 更新
            elif char.isdigit():
                cur_num = cur_num * 10 + int(char)
            else:
                cur_str += char
        return cur_str

时间复杂度：O(n) 空间复杂度：O(n)