Simple python solution using stack with brief explanation


  • 0
    J

    The basic idea is I put each element of the string in a stack. Each time I find a closed bracket, I traverse back until I find the corresponding open bracket. I put whatever between these two brackets in a string str and then I keep poping the stack until I find how much times I should repeat the str. I repeat the str and then put it back to the stack. Keep doing this, I will reach the end of my original string, then the join of all the elements in the stack is the answer.

    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        stack = []
        str = num = ''
        for c in s:
            if c != ']':
                stack.append(c)
            else:
                while stack[-1] != '[':
                    str = stack.pop() + str
                stack.pop()
                while stack and stack[-1].isdigit():
                    num = stack.pop() + num
                num = int(num)
                str = str * num
                stack.append(str)
                num = str = ''
        return "".join(stack)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.