A pattern file compresses repetitive text with a shorthand: k[text] stands for text written k times in a row. Shorthands can be nested, so 2[x3[y]] is 2[xyyy], which is xyyyxyyy.
Write expand(s) that returns the fully expanded text.
scontains lowercase letters, digits and square brackets, and is always well formed.- Digits only ever appear as a repeat count directly before a
[. A count is between1and300and may have several digits. - Letters outside any brackets are copied as they are.
expand("3[ab]c") # "abababc"
expand("2[x3[y]]") # "xyyyxyyy"
expand("a2[b]c2[de]") # "abbcdede"
expand("10[z]") # "zzzzzzzzzz"
expand("hello") # "hello"
Constraints: 1 <= len(s) <= 10^5; the expanded text has at most 2 * 10^5 characters; brackets can be nested up to 25,000 levels deep (much deeper than Python's default recursion limit of about 1,000).
Repeatedly finding an innermost k[...] and substituting it rescans the string once per level of nesting, which is far too slow at this depth. Aim for a single left-to-right pass, doing work proportional to the input plus the output.
Show hint
when you reach a [, you have to put the text built so far on hold and start a fresh piece; when you reach the matching ], you repeat the fresh piece and glue it back onto whatever was on hold. Held pieces come back in the reverse order they were put aside.