Decode String
Decode String is LeetCode 394 (Medium). Given an encoded string s, return its decoded form. The rule is k[encoded_string]: the text inside the brackets is repeated exactly k times.
- Groups can be nested, so an inner group must be expanded before its outer count applies.
kis a positive integer up to 300, so it can have several digits.- The input is always valid, and the original text never contains digits.
- 1 <= s.length <= 30
- s consists of lowercase English letters, digits, and square brackets '[]'.
- s is guaranteed to be a valid input.
- All the integers in s are in the range [1, 300].
- The output length never exceeds 10⁵.
Intuition
When a [ opens, the outer group is only half built: its count and the text before the bracket are known, but its inside is not. So the outer group has to pause while the inner one is finished, and then carry on.
The group opened last always closes first, which is exactly what a stack handles. Save the outer count and text at each [, and at the matching ] take them back and join the pieces. One left-to-right pass decodes any depth of nesting.
Nested, balanced brackets where the inside must be finished before the outside can use it call for a stack that saves the outer context at each opener and restores it at the closer. Decode String shares this shape with Basic Calculator (parentheses with a saved sign and result) and Valid Parentheses.
Approach
Before reading on: in 3[a2[c]], which group must be finished first? While you work on it, what two facts about the outer group must you remember so you can finish that one afterwards?
Two ways to solve it
Scan once, saving the count and the text so far at each [ and rebuilding the string at each ].
- Depth: any nesting, no call stack.
- State: two stacks you can print and check.
- Code: four cases in one loop.
The version most interviewers expect.
A function decodes until it meets ], calling itself at every [ and repeating what the call returns.
- Depth: one call per open bracket.
- State: a shared index into
s. - Code: reads like the grammar.
Same work; the call stack does the saving.
Both do the same work, but the loop keeps the saved levels in plain sight and has no shared index to get wrong, so the steps, code and live demo below follow it. The recursive code comes after the demo.
Fold digits into the count
On a digit, set num = num * 10 + digit. A count like 12 arrives as two characters, so it has to be built up digit by digit and used only when the [ arrives.
Save the outer level at [
Push num and current (the text built so far at this level), then reset both. The count says how often the coming group repeats; the saved text must end up in front of it.
Rebuild at ]
Pop the count k and the saved text, and set current = saved + current * k. The saved text goes first because it was written before the bracket. The result is now ordinary text of the level one out.
Append letters, then return
A letter just extends current. After the last character every bracket has been closed, so the stack is empty and current is the decoded string. The work is proportional to the length of the output.
Decode String solution in Python | C++ | Java
current is the text of the group being built and num the count read so far. The stack will save the outer level each time a group opens, because an inner group must be finished before its outer count can apply.num as num × 10 + 3, not stored on its own: a count like 12 arrives as two characters, and it is only used once the [ shows up.current, the text of the innermost open group. The stack is not touched until a bracket appears.[. The result becomes current again, so the outer text keeps growing from here.num as num × 10 + 2, not stored on its own: a count like 12 arrives as two characters, and it is only used once the [ shows up.current, the text of the innermost open group. The stack is not touched until a bracket appears.current, the text of the innermost open group. The stack is not touched until a bracket appears.[. The result becomes current again, so the outer text keeps growing from here.[ saved a level and its ] restored it, so the stack is empty again and current holds the whole string after one pass.current is the text of the group being built and num the count read so far. The stack will save the outer level each time a group opens, because an inner group must be finished before its outer count can apply.num as num × 10 + 3, not stored on its own: a count like 12 arrives as two characters, and it is only used once the [ shows up.current, the text of the innermost open group. The stack is not touched until a bracket appears.num as num × 10 + 2, not stored on its own: a count like 12 arrives as two characters, and it is only used once the [ shows up.current, the text of the innermost open group. The stack is not touched until a bracket appears.[. The result becomes current again, so it is now part of the group one level out.[. The result becomes current again, so the outer text keeps growing from here.[ saved a level and its ] restored it, so the stack is empty again and current holds the whole string after one pass.current is the text of the group being built and num the count read so far. The stack will save the outer level each time a group opens, because an inner group must be finished before its outer count can apply.num as num × 10 + 2, not stored on its own: a count like 12 arrives as two characters, and it is only used once the [ shows up.current, the text of the innermost open group. The stack is not touched until a bracket appears.current, the text of the innermost open group. The stack is not touched until a bracket appears.[. The result becomes current again, so the outer text keeps growing from here.current, the text of the top level. The stack is not touched until a bracket appears.current, the text of the top level. The stack is not touched until a bracket appears.[ saved a level and its ] restored it, so the stack is empty again and current holds the whole string after one pass.Recursive decode
decode() reads from a shared index i. Letters are appended, digits build the count, a [ calls decode() for the inner group and repeats its result, and a ] returns the group built so far.
Common pitfalls
Reading one digit as the whole count
num = int(ch)
num = num * 10 + int(ch)
Each digit overwrites the last, so 12[a] keeps only the 2 and returns two copies instead of twelve.
Not resetting num after [
count_stack.append(num) string_stack.append(current) current = ""
count_stack.append(num) string_stack.append(current) current, num = "", 0
The old count is still in num, so the next digit is added on top of it: in 3[2[a]] the inner count becomes 32 instead of 2.
Putting the saved text after the group
current = current * count_stack.pop() + string_stack.pop()
current = string_stack.pop() + current * count_stack.pop()
The saved text was written before the [, so it goes in front. Reversed, a2[b] decodes to bba instead of abb.
Edge cases
], 2[a]bcThey extend current at the outer level, giving aabc.
Complexity
Decode String FAQ
Can the Python solution use one stack?
Yes. Keep one stack of [text, count] pairs: on [ push the pair and reset, on ] pop it and set current = text + current * count. It is the same algorithm with the two stacks zipped together; Python's string repetition current * count does the repeating.