MediumNeetCode150StackRecursionString
Decode String
Decode nested encoded string.
Examples
Input
s = "3[a2[c]]"
Output
accaccacc
3 * a2[c] = 3 * acc.
Constraints
- •
1 <= s.length <= 30 - •
s consists of lowercase English letters, digits, []
Approaches
Use stacks for count and string.
CodeT: O(n*k) | S: O(n*k) decoded string
Handle nested brackets.
CodeT: O(n*k) | S: O(n) stack depth
Two stacks: nums and strs.
CodeT: O(n*k) | S: O(n*k)
def decodeString(s):
stack=[]; num=0; cur=''
for c in s:
if c.isdigit(): num=num*10+int(c)
elif c=='[': stack.append((cur,num)); cur=''; num=0
elif c==']':
prev,n=stack.pop(); cur=prev+cur*n
else: cur+=c
return curComplexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Stack | O(n*k) | O(n*k) decoded string | Use stacks for count and string. |
| Recursive | O(n*k) | O(n) stack depth | Handle nested brackets. |
| Stack Optimized | O(n*k) | O(n*k) | Two stacks: nums and strs. |
Stack
T: O(n*k)S: O(n*k) decoded string
Use stacks for count and string.
Recursive
T: O(n*k)S: O(n) stack depth
Handle nested brackets.
Stack Optimized
T: O(n*k)S: O(n*k)
Two stacks: nums and strs.
Common Mistakes
Not handling nested brackets
Off-by-one in count parsing
Wrong stack pop order