LC 0394 [M] Decode String - ALawliet/algorithms GitHub Wiki

class Solution(object):
    def decodeString(self, s):
        stack = []; curNum = 0; curString = ''
        for c in s:
            if c == '[':
                stack.append(curString)
                stack.append(curNum)
                curString = ''
                curNum = 0
            elif c == ']':
                prevNum = stack.pop()
                prevString = stack.pop()
                curString = prevString + prevNum*curString
            elif c.isdigit():
                curNum = curNum*10 + int(c)
            elif c.isalpha():
                curString += c
        return curString

class Solution:
    def decodeString(self, s: str) -> str:
        closePos = {}
        l = []
        for i, c in enumerate(s):
            if c == '[':
                l.append(i)
            elif c == ']':
                closePos[l.pop()] = i

        def parse(l, r):
            mult = 0
            ans = []
            while l <= r:
                c = s[l]
                if c.isdigit():
                    mult = mult*10 + int(c)
                elif c.isalpha():
                    ans.append(c)
                elif c == '[':
                    ans.append(mult * parse(l + 1, closePos[l] - 1))
                    mult = 0
                    l = closePos[l]
                l += 1
            return ''.join(ans)

        return parse(0, len(s) - 1)