NUHMAN.com

Introduction

The problem LeetCode 247: Strobogrammatic Number II is a fascinating follow-up to problem 246. Instead of checking whether a number is strobogrammatic, here we're asked to generate all such numbers of a given length.

This is a classic recursive backtracking problem with symmetry involved. Let’s break it down clearly.

Problem Statement

Given an integer n, return all the strobogrammatic numbers that are of length n. You may return the answer in any order.

Example:

vbnet

Input: n = 2
Output: ["11","69","88","96"]

Input: n = 1
Output: ["0","1","8"]

Step-by-Step Solution in Python

Step 1: Understand the Strobogrammatic Digit Pairs

To build valid numbers, we need to know what digit pairs are strobogrammatic:

• ('0', '0')
• ('1', '1')
• ('6', '9')
• ('8', '8')
• ('9', '6')

These pairs can be added to the beginning and end of a number to maintain strobogrammatic symmetry.

Step 2: Use Recursive Backtracking

We’ll use recursion to build numbers from the outside in:

• Base cases: return [""] for n = 0, and ["0", "1", "8"] for n = 1
• For longer numbers, insert valid pairs around all smaller valid numbers

We must also be careful to not use '0' at the beginning of numbers (except for single-digit numbers).

Step 3: Code It

python

def findStrobogrammatic(n: int) -> list[str]:
    # Define valid pairs
    pairs = [('0','0'), ('1','1'), ('6','9'), ('8','8'), ('9','6')]

    # Recursive helper function
    def build(n, final_length):
        if n == 0:
            return [""]
        if n == 1:
            return ["0", "1", "8"]
        
        prev = build(n - 2, final_length)
        result = []

        for middle in prev:
            for a, b in pairs:
                if n != final_length or a != '0':  # Avoid leading zero
                    result.append(a + middle + b)

        return result

    return build(n, n)

Explanation of the Code

1. Valid Pairs:
2. Defined all digit pairs that maintain their shape when rotated.
3. Recursive Build Function:

• If n == 0: return [""] (base for even-length).
• If n == 1: return single-digit strobogrammatic numbers.
• Otherwise, build from smaller substrings and surround with valid digit pairs.

1. Avoid Leading Zeros:
2. Ensure the first digit isn't '0' unless the whole number is of length 1.

Example Walkthrough (n = 2)

• Base case for n=0: [""]
• Build n=2: Insert all valid pairs around "" →
• → "00", "11", "69", "88", "96"
• Remove "00" since leading '0' is invalid → Final:
• → ["11", "69", "88", "96"]

Time and Space Complexity

• Time Complexity: O(5^(n/2)) – Each level adds 5 pairs, and we recurse roughly n/2 levels.
• Space Complexity: O(5^(n/2)) – The number of valid strings generated is exponential in n.

Conclusion

LeetCode 247 is a great exercise in recursive backtracking and understanding symmetry. The elegant part is how you build the number layer by layer from the inside out using valid mirrorable digit pairs.