MediumNo. 0394
Decode String — LeetCode 394 Python Solution
- Pattern
- Stack
- Topics
- Stack, Recursion, String
- On a study list
- LeetCode 75
- Reading time
- 3 min
- Source
- leetcode.com
The problem
Given an encoded string, return its decoded string. The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times.
Example
- Input
- s = "3[a]2[bc]"
- Output
- "aaabcbc"
Python solution
class Solution:
def decodeString(self, s: str) -> str:
s1, s2 = [], []
num, res = 0, ''
for c in s:
if c.isdigit():
num = num * 10 + int(c)
elif c == '[':
s1.append(num)
s2.append(res)
num, res = 0, ''
elif c == ']':
res = s2.pop() + res * s1.pop()
else:
res += c
return resComplexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Stack
When the most recent unresolved thing is the one that matters, use a stack. LeetCode 394. Decode String is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Stack.
The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0224 | Basic Calculator | Hard |
| 1106 | Parsing A Boolean Expression | Hard |
| 0388 | Longest Absolute File Path | Medium |
| 0385 | Mini Parser | Medium |
| 0020 | Valid Parentheses | Easy |
| 0071 | Simplify Path | Medium |
Frequently asked questions
- How hard is LeetCode 394. Decode String?
LeetCode 394. Decode String is rated Medium on LeetCode.
- What is the time complexity of LeetCode 394. Decode String?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 394. Decode String?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 394. Decode String cover?
LeetCode 394. Decode String is tagged Stack, Recursion and String on LeetCode.