⚡Flashcard Drill➔
NeetCode #513LC-247MediumBacktrackingNC Algo100
← Back to All Problems

#513 · #247 · Strobogrammatic Number II(中心对称数 II)

📌 Problem Statement & Constraints

Given an integer n, return all strobogrammatic numbers of length n in any order. A strobogrammatic number looks the same when rotated 180 degrees; the valid digit pairs are 0-0, 1-1, 6-9 and 8-8. Constraints: 1 <= n <= 14.

💡 Core Algorithmic Approaches

  1. Build the number from the outside in: each step wraps an inner strobogrammatic string with a valid pair.
  2. The base cases are the empty string (even length) and the single digits 0, 1, 8 (odd length).
  3. Leading zeros are forbidden at the outermost level, so the 0-0 pair is excluded when building a full-length number.
  4. The recursion builds length k from length k - 2, which naturally handles both parities.

💻 Benchmark Python3 Implementation

class Solution:
    def findStrobogrammatic(self, n: int) -> List[str]:
        pairs = [("0", "0"), ("1", "1"), ("6", "9"), ("8", "8"), ("9", "6")]

        def build(k: int) -> List[str]:
            if k == 0:
                return [""]                # even-length base
            if k == 1:
                return ["0", "1", "8"]     # odd-length base (self-symmetric digits)
            res = []
            for mid in build(k - 2):
                for a, b in pairs:
                    if k == n and a == "0":
                        continue           # no leading zero at the outermost level
                    res.append(a + mid + b)
            return res

        return build(n)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(5^(n/2) * n): the number of strobogrammatic strings grows exponentially in n/2.
💾 Space Complexity
O(n) for the recursion depth plus the output.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the leading-zero restriction: numbers like "00" and "010" would be produced.
  • Applying the leading-zero rule at every level: "1001" is valid, and its inner "00" is legitimate -- the restriction applies only at the outermost wrap.
  • Missing the odd-length base case: n = 1 must yield 0, 1, 8.
  • Building from the inside out: either direction works, but outside-in makes the leading-zero rule easy to state.
⚡
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 Backtracking Problems