141. Unpack the Nest
A message is stored in a packed form. A nest is written as k[text], which stands for text repeated exactly k times, where k is a positive whole number. Nests can sit inside other nests, and plain lower case letters can stand next to them or inside them. Digits only appear as the number in front of an opening bracket.
Given the packed message s, which is always well formed, return the unpacked text. A stack that remembers the text built so far and the repeat count of every open bracket solves it in one pass.
Example 1
- Input:
- s = "2[x3[yz]]w"
- Output:
- "xyzyzyzxyzyzyzw"
- Explanation:
The inner nest gives yzyzyz, so the outer text is xyzyzyz; two copies of it followed by w make xyzyzyzxyzyzyzw.
Example 2
- Input:
- s = "10[q]"
- Output:
- "qqqqqqqqqq"
- Explanation:
The letter q is repeated ten times.
Constraints
1 ≤ s.length ≤ 105
s contains lower case letters, digits and square brackets
1 ≤ k ≤ 300, and the unpacked text has at most 105 characters
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n + m)
- Space
- O(n + m)