LC 394

Stack
Stack
Publish Date:   2022-06-27

Solutions to LeetCode 394 Decode String.

LeetCode 394

Decode String (Medium) [link]

Time complexity O(n). Space complexity O(n).

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        mul = 0
        res = ''
        for c in s:
            if c == '[':
                stack.append([mul, res])
                mul = 0
                res = ''
            elif c == ']':
                cur_mul, pre_res = stack.pop()
                res = pre_res + cur_mul * res
            elif "0" <= c <= "9":
                mul = mul * 10 + int(c)
            else:
                res += c
        return res
Stack
  TOC