Problem Description

Given an integer n, you need to find all possible strobogrammatic numbers that have exactly n digits.

A strobogrammatic number is a number that looks the same when rotated 180 degrees (viewed upside down). For example:

• The digit 0 rotated 180° still looks like 0
• The digit 1 rotated 180° still looks like 1
• The digit 8 rotated 180° still looks like 8
• The digit 6 rotated 180° becomes 9
• The digit 9 rotated 180° becomes 6

Other digits (2, 3, 4, 5, 7) don't have valid rotations that form readable digits.

For a number to be strobogrammatic, when you rotate the entire number 180 degrees, it must read the same as the original. This means:

• The first digit must match with the last digit after rotation
• The second digit must match with the second-to-last digit after rotation
• And so on...

For example:

• 69 is strobogrammatic because when rotated, 6 becomes 9 and 9 becomes 6, giving us 69 when read from left to right
• 88 is strobogrammatic because 8 rotated is still 8
• 818 is strobogrammatic because the middle 1 stays as 1, and the outer 8s remain as 8s

You should return all valid strobogrammatic numbers of length n. The numbers can be returned in any order.

Note: Leading zeros are not allowed in the final result (except for the number "0" itself when n=1).

Intuition

The key insight is that strobogrammatic numbers have a symmetric structure. When building a strobogrammatic number, we need to ensure that digits on opposite ends form valid pairs when one is rotated 180 degrees.

Let's think about what pairs of digits work:

• (0, 0) - zero rotated is still zero
• (1, 1) - one rotated is still one
• (6, 9) - six rotated becomes nine
• (8, 8) - eight rotated is still eight
• (9, 6) - nine rotated becomes six

This symmetric property suggests we can build these numbers from the outside in. If we have a strobogrammatic number of length n-2, we can create strobogrammatic numbers of length n by wrapping valid digit pairs around it.

For example, if "1" is a strobogrammatic number of length 1, we can create length 3 numbers by adding pairs:

• "111" (wrapping with (1,1))
• "818" (wrapping with (8,8))
• "619" (wrapping with (6,9))
• "916" (wrapping with (9,6))

This naturally leads to a recursive approach:

• Base cases: For length 0, we have an empty string. For length 1, only "0", "1", and "8" work (since they look the same when rotated).
• Recursive case: For length n, take all strobogrammatic numbers of length n-2 and wrap each valid digit pair around them.

There's one special consideration: we can wrap (0,0) around inner numbers, but this creates leading zeros. Leading zeros are only valid for intermediate recursive calls, not for the final result. So we only add "0...0" wrapping when we're building intermediate results (when u != n), not when building the final answer of length n.

This recursive structure naturally handles all cases - odd lengths will have a middle digit that must be self-symmetric (0, 1, or 8), while even lengths will be built entirely from pairs.

Solution Approach

The solution implements a recursive approach using a helper function dfs(u) that generates all strobogrammatic numbers of length u.

Base Cases:

• When u = 0: Return [''] (list with empty string) - this serves as the foundation for building longer numbers
• When u = 1: Return ['0', '1', '8'] - these are the only single digits that look the same when rotated 180 degrees

Recursive Case (u > 1):

1. First, recursively get all strobogrammatic numbers of length u - 2 by calling dfs(u - 2)
2. For each number v from the previous step, wrap it with valid digit pairs:
   • Wrap with ('1', '1') to create '1' + v + '1'
   • Wrap with ('8', '8') to create '8' + v + '8'
   • Wrap with ('6', '9') to create '6' + v + '9'
   • Wrap with ('9', '6') to create '9' + v + '6'

Handling Leading Zeros: The pair ('0', '0') is also valid, but we need to be careful about leading zeros:

• If u != n (we're building an intermediate result, not the final answer), we can add '0' + v + '0'
• If u == n (we're building the final result), we skip the ('0', '0') pair to avoid numbers with leading zeros

Example Walkthrough for n = 3:

1. dfs(3) is called
2. It calls dfs(1), which returns ['0', '1', '8']
3. For each value in ['0', '1', '8'], we wrap with valid pairs:
   • For '0': creates '101', '808', '609', '906'
   • For '1': creates '111', '818', '619', '916'
   • For '8': creates '181', '888', '689', '986'
4. Since u == n, we don't add wrappings with '0' on both ends
5. Final result: ['101', '111', '181', '609', '619', '689', '808', '818', '888', '906', '916', '986']

The algorithm builds numbers layer by layer from the center outward, ensuring each layer maintains the strobogrammatic property. The time complexity is O(5^(n/2)) since we have at most 5 choices for each pair (including '00' for intermediate steps), and we need n/2 pairs.

Example Walkthrough

Let's walk through finding all strobogrammatic numbers of length n = 2.

Step 1: Initial Call

• We call dfs(2) to find all 2-digit strobogrammatic numbers

Step 2: Recursive Call

• Since u = 2 > 1, we need to call dfs(2 - 2) = dfs(0)
• dfs(0) returns [''] (base case: empty string)

Step 3: Build Numbers by Wrapping Pairs

• We take each result from dfs(0) (just the empty string '') and wrap it with valid digit pairs:
  • '1' + '' + '1' = '11'
  • '8' + '' + '8' = '88'
  • '6' + '' + '9' = '69'
  • '9' + '' + '6' = '96'

Step 4: Check for Leading Zeros

• Since u = 2 equals n = 2 (we're building the final result), we do NOT add '0' + '' + '0' = '00' because it would have a leading zero

Final Result: ['11', '88', '69', '96']

Let's verify these are strobogrammatic:

• 11 → rotate 180° → 11 ✓
• 88 → rotate 180° → 88 ✓
• 69 → rotate 180° → 69 (6→9, 9→6) ✓
• 96 → rotate 180° → 96 (9→6, 6→9) ✓

Now let's trace through a slightly more complex example with n = 4:

Step 1: Call dfs(4)

Step 2: This calls dfs(2), which we already computed above: ['11', '88', '69', '96']

• Note: When dfs(2) was called as an intermediate step (u=2, but n=4), it would also include '00' in its result, giving us ['00', '11', '88', '69', '96']

Step 3: Wrap each 2-digit result with valid pairs:

• From '00': → '1001', '8008', '6009', '9006'
• From '11': → '1111', '8118', '6119', '9116'
• From '88': → '1881', '8888', '6889', '9886'
• From '69': → '1691', '8698', '6699', '9696'
• From '96': → '1961', '8968', '6969', '9966'

Step 4: Since u = 4 = n, we don't add '0' + ... + '0' wrappings to avoid leading zeros

Final Result: 20 four-digit strobogrammatic numbers

Solution Implementation

Time and Space Complexity

Time Complexity: O(5^(n/2))

The algorithm uses recursion to build strobogrammatic numbers from the inside out. At each recursive level (which decreases by 2 each time), we have at most 5 choices for pairs to add: ('11', '88', '69', '96', '00'). The recursion depth is n/2 since we reduce u by 2 in each recursive call until reaching the base cases.

• For each recursive call at depth d, we process all strings from depth d-1
• At depth d, there are at most 5^d strings being generated
• Each string operation (concatenation) takes O(n) time
• Total time complexity: O(n * 5^(n/2)), which can be simplified to O(5^(n/2)) since the exponential term dominates

Space Complexity: O(n * 5^(n/2))

The space complexity consists of:

• Recursion call stack: O(n/2) = O(n) depth
• Storage for results: At the final level, we store all valid strobogrammatic numbers. The maximum number of valid n-digit strobogrammatic numbers is bounded by 5^(n/2), and each string has length n
• Intermediate results: During recursion, we maintain lists of partial results at each level, but these are dominated by the final result size

Therefore, the total space complexity is O(n * 5^(n/2)) to store all the generated strings.

Common Pitfalls

Pitfall 1: Incorrectly Handling Leading Zeros

The Problem: A common mistake is forgetting to handle the leading zero case properly. Developers might either:

1. Always include ('0', '0') pairs, resulting in invalid numbers like "00100" for n=5
2. Never include ('0', '0') pairs, missing valid intermediate constructions needed for the recursion

Why It Happens: The digit '0' is strobogrammatic (looks the same when rotated), so it seems natural to always include it with other valid pairs. However, numbers shouldn't have leading zeros (except "0" itself when n=1).

Incorrect Implementation:

# WRONG: Always adding '0' pairs
for inner in inner_numbers:
    for left_digit, right_digit in [('0', '0'), ('1', '1'), ('8', '8'), ('6', '9'), ('9', '6')]:
        result.append(left_digit + inner + right_digit)

Correct Solution: The key insight is that '0' pairs can be used in intermediate recursive calls but not in the final layer. The condition if remaining_length != n: ensures we only add zeros when building inner layers:

for inner in inner_numbers:
    # Add non-zero pairs
    for left_digit, right_digit in [('1', '1'), ('8', '8'), ('6', '9'), ('9', '6')]:
        result.append(left_digit + inner + right_digit)
  
    # Only add '0' pairs for intermediate layers
    if remaining_length != n:  # This check is crucial!
        result.append('0' + inner + '0')

Pitfall 2: Misunderstanding the Base Cases

The Problem: Developers might incorrectly define base cases, such as:

1. Returning [''] for both n=0 and n=1
2. Forgetting that n=1 should return actual single-digit strobogrammatic numbers
3. Including invalid single digits like '6' or '9' alone for n=1

Why It Happens: The digits '6' and '9' are part of strobogrammatic pairs, but individually they don't look the same when rotated 180 degrees. Only '0', '1', and '8' maintain their appearance when rotated alone.

Incorrect Implementation:

# WRONG: Including 6 and 9 as valid single digits
if remaining_length == 1:
    return ['0', '1', '6', '8', '9']  # 6 and 9 alone are NOT strobogrammatic!

Correct Solution:

if remaining_length == 0:
    return ['']  # Foundation for building longer numbers
if remaining_length == 1:
    return ['0', '1', '8']  # Only these look the same when rotated alone

Pitfall 3: Forgetting Edge Cases

The Problem: Not properly handling special cases like n=1 where "0" is a valid answer despite the "no leading zeros" rule.

Why It Happens: The general rule "no leading zeros" has an exception: the number "0" itself is valid when n=1. This edge case is easy to overlook.

Solution: The recursive approach naturally handles this because:

• When n=1, the function directly returns ['0', '1', '8'] from the base case
• The leading zero check if remaining_length != n: is never reached for n=1
• This ensures "0" is included in the result for n=1 while preventing leading zeros for n>1