Decode String
Medium
Given an encoded string s, decode it and return the decoded string.
The encoding rule is:
k[encoded_string]
where encoded_string inside the square brackets is repeated exactly k times.
You may assume that:
- The input is always valid.
- There are no extra spaces.
- Digits are used only for repetition counts.
Example 1
Input
s = "3[a]2[bc]"
Output
"aaabcbc"
Explanation
3[a] → aaa
2[bc] → bcbc
Combining them:
aaabcbc
Example 2
Input
s = "3[a2[c]]"
Output
"accaccacc"
Explanation
First decode:
2[c] → cc
So:
a2[c] → acc
Then repeat three times:
accaccacc
Constraints
1 <= s.length <= 30
s consists of lowercase English letters
digits
and square brackets.
1 <= k <= 300
The encoded string is valid.
The decoded string length will not exceed 10^5.
Hints:
Hint 1
Use a stack to keep track of the strings and repetition counts when encountering [.
Hint 2
When you encounter a digit, build the complete repetition number.
When you encounter ], pop the previous string and repeat the current string the required number of times.
Auto
Loading editor...
Input
Expected Output