Decode String

Intuition

Nesting is what makes this tricky, and a stack is the natural tool for nesting. As we read characters we build up a current string. When we hit an opening bracket we must remember what we had before it plus the number that will multiply the upcoming block, so we push both and reset. On a closing bracket we pop the saved prefix and multiplier, expand the block we just finished, and attach it back. Digits may span several characters, so we accumulate them into a running number.

Algorithm walkthrough

1. 1Maintain a current string buffer, a running number, and two stacks for saved strings and saved counts.
2. 2For each digit, extend the running number as num = num * 10 + digit.
3. 3On '[', push the current buffer and the running number, then reset both.
4. 4On ']', pop the saved count k and saved prefix, and set the buffer to prefix followed by k copies of the buffer.
5. 5For a letter, append it to the buffer; after the whole scan, the buffer holds the decoded string.

Implementation

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        cur = ""
        num = 0
        for c in s:
            if c.isdigit():
                num = num * 10 + int(c)
            elif c == '[':
                stack.append((cur, num))
                cur = ""
                num = 0
            elif c == ']':
                prev, k = stack.pop()
                cur = prev + cur * k
            else:
                cur += c
        return cur