Decode String
Given an encoded string, return its decoded string (e.g., 3[a]2[bc] -> aaabcbc).
- 1 <= s.length <= 30
- s consists of lowercase English letters, digits, and square brackets
- s is guaranteed to be a valid input
s = "3[a]2[bc]""aaabcbc"s = "3[a2[c]]""accaccacc"3[a2[c]] says: repeat a2[c] three times. But you can't do that until you know what a2[c] expands to — and that needs 2[c] first. The outer job is blocked on the inner one, and the innermost job has to finish before anything wrapping it can. So while you work on an inner piece, you need somewhere to park the outer piece you paused, and you always return to the most recently paused one.
"Resume the most recently paused job first" is what a stack does. A stack is a pile you touch only from the top — push to set something aside on top, pop to take the top thing back, last-in-first-out. Park each paused outer job on the stack.
As you scan, carry two things: current, the string you're building right now, and k, the number sitting in front of the current bracket. The stack stores paused outer jobs as (text_so_far, repeat_count) pairs.
- A digit → grow k (numbers can be multi-digit: k = k 10 + digit).
- [ → a new inner job begins. Push (current, k) to remember where you were, then reset current = "" and k = 0 to build the inner piece from scratch.
- A letter → append it to current.
- ] → the inner job is done. Pop (prev, num), then set current = prev + current num: repeat the finished inner piece num times and glue it after the outer text you had paused.
def decode_string(s):
stack = [] # paused outer jobs: (text_so_far, repeat_count)
current = ""
k = 0
for ch in s:
if ch.isdigit():
k = k * 10 + int(ch)
elif ch == '[':
stack.append((current, k)) # pause the outer job
current, k = "", 0 # start the inner job fresh
elif ch == ']':
prev, num = stack.pop() # resume the outer job
current = prev + current * num
else:
current += ch
return current], the multiplier you use is the one popped from the stack — not the live k. The number that scales an inner string was the one written in front of its own [, and that got saved on the stack when the bracket opened; the current k belongs to some deeper bracket entirely. Reading the wrong one is the classic bug here. And don't forget to reset both current and k right after you push.3 → k=3 · [ → push ("", 3), reset · a → current="a"2 → k=2 · [ → push ("a", 2), reset · c → current="c"] → pop ("a", 2): current = "a" + "c"×2 = "acc"] → pop ("", 3): current = "" + "acc"×3 = "accaccacc"Each ] collapses a finished inner piece into the outer text and pops back up one level. The stack is what remembers every outer job you paused on the way down, so no matter how deeply the brackets nest, you always resume the right one.
Dual-Stack Checkpointing for Nested Structures
Decoding '3[a]2[bc]'. Prepare stacks for nested expansion.
Use stacks to "checkpoint" the current state (string and multiplier) before diving into a nested bracket.