Decode Nested Repeats
Problem
An encoded text uses the form k[segment], meaning the segment is repeated k times. The repeat count k is a positive whole number that may have several digits, and a segment may itself contain further encoded segments. Expand the encoding and return the plain text.
Examples
Input: text = "3[a]2[bc]"
Output: "aaabcbc"Input: text = "2[ab3[c]]"
Output: "abcccabccc"
Why: the inner segment expands first, then the outer one repeats the resultInput: text = "xyz"
Output: "xyz"
Why: edge case, text with no encoding passes through unchangedHints
0 / 3
Nesting means an outer repeat cannot be finished until everything inside it is finished, which is the same shape as a function waiting for the calls it made.
When an opening bracket arrives, the text built so far and the count just read must be set aside and picked up again later, in reverse order of arrival.
Build characters into a current buffer. On a digit, extend the number being read, allowing several digits. On an opening bracket, push the current buffer and count onto a stack and start fresh. On a closing bracket, pop the parked buffer and count, append the finished segment to it that many times, and continue from there.
Solution
Brackets nest, so the contexts they open must be closed in reverse order, which is exactly what a stack provides. Each opening bracket parks the text built so far together with the count that applies to the segment about to start, and each closing bracket retrieves them and folds the finished segment in. Digits are accumulated as a running number so multi-digit counts work, and text with no brackets simply never touches the stack. Time is O(length of the output) and space is O(depth of nesting plus the output).
def decode_repeats(text):
stack, current, count = [], [], 0
for ch in text:
if ch.isdigit():
count = count * 10 + int(ch) # a count may span several digits
elif ch == "[":
stack.append((current, count)) # park the outer context
current, count = [], 0
elif ch == "]":
outer, times = stack.pop() # resume the context we parked
outer.append("".join(current) * times)
current = outer
else:
current.append(ch)
return "".join(current)
print(decode_repeats("3[a]2[bc]")) # -> aaabcbc
print(decode_repeats("2[ab3[c]]")) # -> abcccabccc
print(decode_repeats("xyz")) # -> xyzStuck on the idea rather than the code? Stack Basics covers it.