NeetCode #359LC-394MediumStackNC 250
← Back to All Problems#359 · #394 · Decode String(字符串解码)
📌 Problem Statement & Constraints
Given an encoded string, return its decoded form. The encoding rule is
k[encoded_string], meaning the enclosed string repeats exactly k times. Brackets may be nested and k is a positive integer. Constraints: 1 <= s.length <= 30, 1 <= k <= 300; the input is always valid.💡 Core Algorithmic Approaches
- Use a stack of
(previous_string, repeat_count)pairs. - On a digit, accumulate the number (it can be multi-digit).
- On
[, push the current string and count, then reset both. - On
], pop and prepend the saved string to the current string repeatedktimes.
💻 Benchmark Python3 Implementation
class Solution:
def decodeString(self, s: str) -> str:
st = []
cur = ""
num = 0
for ch in s:
if ch.isdigit():
num = num * 10 + int(ch) # multi-digit counts
elif ch == "[":
st.append((cur, num)) # save the outer context
cur = ""
num = 0
elif ch == "]":
prev, k = st.pop()
cur = prev + cur * k # expand
else:
cur += ch
return cur⚡ Complexity Deep Dive
⏱️ Time Complexity
O(L) where L is the length of the decoded string: each character is appended once.
💾 Space Complexity
O(d) for the stack, where d is the nesting depth, plus O(L) for the output.
⚠️ Interview Pitfalls & Follow-ups
- Assuming single-digit counts:
12[a]is valid, so the number must be accumulated. - Pushing only the count: the outer string must also be saved, otherwise the prefix is lost.
- Forgetting to reset
numafter[: the next count would be concatenated onto the previous one. - Using recursion: it works, but the iterative stack version avoids any depth concerns.
- Trying to find matching brackets with
index/rindex: nested brackets break naive matching.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.