Decode Nested String

Use a stack to decode strings like 3[a2[b]] into aaabbb.

stack string parsing recursion

Given an encoded string, return its decoded string. The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is repeated exactly k times. Note that k is guaranteed to be a positive integer. The input string is always valid; there are no extra spaces, and the brackets are well-formed. You may assume that the encoded string does not contain digits outside the brackets, except as the repetition numbers. Implement the function `decode_string(s: str) -> str` that takes the encoded string and returns the fully decoded string.

Constraints

1 <= len(s) <= 1000. s consists of lowercase English letters, digits, and square brackets '[' and ']'. The input is always valid. The answer is guaranteed to fit in a string of length at most 1000.

Example

>>> decode_string("3[a]2[bc]")
'aaabcbc'
>>> decode_string("3[a2[c]]")
'accaccacc'
>>> decode_string("2[abc]3[cd]ef")
'abcabccdcdcdef'

25 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use a stack to store the current string and the repeat count when encountering '['.

When you see ']', pop the count and the previous string, then append the current string repeated count times.

Build the current string as you scan; handle multi-digit numbers by accumulating digits.

The digits only appear before '[' and the letters are lowercase.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.