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
- Build the number from the outside in: each step wraps an inner strobogrammatic string with a valid pair.
- The base cases are the empty string (even length) and the single digits 0, 1, 8 (odd length).
- Leading zeros are forbidden at the outermost level, so the 0-0 pair is excluded when building a full-length number.
- The recursion builds length
kfrom lengthk - 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 = 1must yield0,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.