LeetCode 394 · Stack

Decode String, explained with a picture

Unwrapping nested gift boxes.

Stack
▶ Watch it step by step

The problem

Decode a string where k[text] means “text repeated k times”, possibly nested.

Input:  "3[a2[c]]"
Output: "accaccacc"

Picture it

Picture nested gift boxes: each says how many copies of its contents to make. Opening a box ([) puts what we had so far and the repeat count on a stack. Closing it (]) repeats the inner text and glues it back onto what we saved.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

Stack of (previous text, count). O(output length).

Python solution

def decode(s):
    stack, cur, k = [], "", 0
    for ch in s:
        if ch.isdigit():
            k = k * 10 + int(ch)
        elif ch == "[":
            stack.append((cur, k))
            cur, k = "", 0
        elif ch == "]":
            prev, times = stack.pop()
            cur = prev + cur * times
        else:
            cur += ch
    return cur

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.