⚡Flashcard Drill➔
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

  1. Use a stack of (previous_string, repeat_count) pairs.
  2. On a digit, accumulate the number (it can be multi-digit).
  3. On [, push the current string and count, then reset both.
  4. On ], pop and prepend the saved string to the current string repeated k times.

💻 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 num after [: 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.
🎯 Drill This Card Now➔

🧩 Related Stack Problems