LeetCode 247: Strobogrammatic Number II Solution in Python – A Step-by-Step Guide

What Is LeetCode 247: Strobogrammatic Number II?

In LeetCode 247: Strobogrammatic Number II, you’re given an integer n, and your task is to return a list of all strobogrammatic numbers of length n. This builds on LeetCode 246: Strobogrammatic Number, shifting from validation to generation, making it a creative twist on string construction.

Problem Statement

• Input: An integer n representing the length of the numbers.
• Output: A list of strings, each a strobogrammatic number of length n.
• Rules: Valid digits are 0, 1, 6, 8, 9; 6 rotates to 9, 9 to 6, 0, 1, 8 stay the same; no leading zeros unless n = 1.

Constraints

• n: 1 to 14.
• Output numbers fit within constraints of string representation.

Examples

• Input: n = 2
• Output: ["11", "69", "88", "96"]
• Input: n = 1
• Output: ["0", "1", "8"]
• Input: n = 3
• Output: ["101", "111", "181", "609", "619", "689", "808", "818", "888", "906", "916", "986"]

Understanding the Problem: Generating Flippable Numbers

To solve LeetCode 247: Strobogrammatic Number II in Python, we need to generate all numbers of length n that look the same when rotated 180 degrees. The valid digits and their rotations are:

• 0 → 0
• 1 → 1
• 6 → 9
• 8 → 8
• 9 → 6

We must pair digits from the outside in (e.g., first with last), and for odd lengths, the middle digit must be self-symmetric (0, 1, 8). We’ll use two methods: 1. Best Solution (Backtracking): O(5^(n/2)) time—efficient and elegant. 2. Alternative Solution (Iterative): O(5^(n/2)) time—systematic but less flexible.

Let’s dive into the best solution with extra detail for beginners.

Best Solution: Backtracking Approach

Why This Is the Best Solution

The backtracking approach shines for LeetCode 247 because it builds numbers symmetrically from the outside in, ensuring each step respects the strobogrammatic property. It’s efficient, naturally handles edge cases (like no leading zeros), and is adaptable to variations, making it the top choice.

How It Works

Think of this solution as building a number like a sandwich: you start with the bread (outer digits) and work inward, adding layers (digit pairs) that match when flipped. If the sandwich has an odd number of layers, the middle is a single ingredient (0, 1, or 8). Here’s how it works, explained simply:

• Base Idea: A strobogrammatic number is symmetric. For length 4 (e.g., "1881"), the first digit (1) pairs with the last (1), the second (8) with the second-to-last (8). For length 3 (e.g., "181"), the middle (8) stands alone.
• Pairs: Use digit pairs that work when rotated: (1, 1), (6, 9), (8, 8), (9, 6), and (0, 0) inside but not at the start.
• Backtracking Process:
• Start with two pointers: left at the beginning, right at the end.
• Add a pair of digits (e.g., 1 and 1) at left and right.
• Move inward and repeat until left meets or passes right.
• For odd n, the middle digit must be 0, 1, or 8.
• No Leading Zeros: Skip 0 for the first digit unless n = 1.
• Helper Function: Use a recursive function to build numbers of length n by filling positions and checking the remaining length.

Step-by-Step Example

Example: n = 2

• Setup: Need numbers of length 2. Start with left = 0, right = 1.
• Pairs: (1, 1), (6, 9), (8, 8), (9, 6)—no (0, 0) because it’s a leading zero.
• Build:
• Try 1 at 0, 1 at 1 → "11".
• Try 6 at 0, 9 at 1 → "69".
• Try 8 at 0, 8 at 1 → "88".
• Try 9 at 0, 6 at 1 → "96".
• Result: ["11", "69", "88", "96"].

Example: n = 3

• Setup: left = 0, right = 2, middle at 1.
• Outer Pairs: (1, 1), (6, 9), (8, 8), (9, 6).
• Middle: 0, 1, 8.
• Build:
• Outer 1, 1:
• Middle 0 → "101".
• Middle 1 → "111".
• Middle 8 → "181".
• Outer 6, 9:
• Middle 0 → "609".
• Middle 1 → "619".
• Middle 8 → "689".
• Outer 8, 8:
• Middle 0 → "808".
• Middle 1 → "818".
• Middle 8 → "888".
• Outer 9, 6:
• Middle 0 → "906".
• Middle 1 → "916".
• Middle 8 → "986".
• Result: ["101", "111", "181", "609", "619", "689", "808", "818", "888", "906", "916", "986"].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down for beginners:

Copy codeclass Solution:
    def findStrobogrammatic(self, n: int) -> List[str]:
        # Step 1: Define our digit pairs
        pairs = [('0', '0'), ('1', '1'), ('6', '9'), ('8', '8'), ('9', '6')]

        # Step 2: Helper function to build numbers
        def build_numbers(length, target_length):
            # Base case: length 0 (even n, done)
            if length == 0:
                return [""]
            # Base case: length 1 (odd n, middle digit)
            if length == 1:
                return ["0", "1", "8"]

            # Step 3: Build by adding pairs
            result = []
            # Recursively get inner part
            inner = build_numbers(length - 2, target_length)
            for left_digit, right_digit in pairs:
                # Skip leading zero for full length
                if left_digit == '0' and length == target_length:
                    continue
                # Add each inner number with outer pair
                for num in inner:
                    result.append(left_digit + num + right_digit)

            return result

        # Step 4: Start building with n
        return build_numbers(n, n)

• Time Complexity: O(5^(n/2))—exponential, as we add pairs (5 choices) for half the length.
• Space Complexity: O(5^(n/2))—storing all results.

This method is like crafting a puzzle, piece by piece—it’s fun once you get it!

Alternative Solution: Iterative Approach

Why an Alternative Approach?

The iterative approach builds numbers step-by-step, starting small and growing to length n. It’s less elegant than backtracking but easier to follow linearly, making it a good alternative for beginners who prefer loops over recursion.

How It Works

• Start with base cases (length 1 or 0).
• Iteratively extend numbers by adding valid pairs, avoiding leading zeros at the full length.

Step-by-Step Example

Example: n = 2

• Length 0: [""].
• Length 2: Add pairs to "":
• 1, 1 → "11".
• 6, 9 → "69".
• 8, 8 → "88".
• 9, 6 → "96".
• Result: ["11", "69", "88", "96"].

Code for Iterative Approach

Copy codeclass Solution:
    def findStrobogrammatic(self, n: int) -> List[str]:
        # Step 1: Define pairs
        pairs = [('0', '0'), ('1', '1'), ('6', '9'), ('8', '8'), ('9', '6')]

        # Step 2: Handle base cases
        if n == 1:
            return ["0", "1", "8"]
        if n == 0:
            return [""]

        # Step 3: Build iteratively
        result = [""]
        for length in range(2, n + 1, 2):
            new_result = []
            for num in result:
                for left_digit, right_digit in pairs:
                    if left_digit == '0' and length == n:
                        continue
                    new_result.append(left_digit + num + right_digit)
            result = new_result

        # Step 4: Add middle digit if n is odd
        if n % 2 == 1:
            new_result = []
            for num in result:
                for mid in ["0", "1", "8"]:
                    new_result.append(num[:len(num)//2] + mid + num[len(num)//2:])
            result = new_result

        return result

• Time Complexity: O(5^(n/2))—similar growth.
• Space Complexity: O(5^(n/2))—storing results.

It’s systematic but less flexible.

Comparing the Two Solutions

• Best Solution (Backtracking):
• Pros: Elegant, adaptable, O(5^(n/2)) time.
• Cons: Recursion might confuse some.
• Alternative Solution (Iterative):
• Pros: Linear flow, easy to trace.
• Cons: Clunkier for odd lengths.

Backtracking wins for elegance.

Additional Examples and Edge Cases

Smallest

• n = 1 → ["0", "1", "8"]

Even Length

• n = 4 → ["1001", "1111", "1691", "1881", "1961", "6009", ...]

No Leading Zeros

• n = 2 excludes "00".

Both handle these well.

Complexity Breakdown

• Backtracking:
• Time: O(5^(n/2))—pair combinations.
• Space: O(5^(n/2))—results.
• Iterative:
• Time: O(5^(n/2))—similar.
• Space: O(5^(n/2))—results.

Both are comparable, but backtracking is cleaner.

Key Takeaways for Beginners

• Backtracking: Build symmetrically, step-by-step.
• Pairs: Use 0-0, 1-1, 6-9, 8-8, 9-6.
• Iterative: Grow numbers gradually.
• Python Tip: Recursion simplifies symmetry—see [Python Basics](/python/basics).

Final Thoughts: Craft Flippable Numbers Like a Pro

LeetCode 247: Strobogrammatic Number II in Python is a creative number-building challenge. The backtracking solution offers elegance, while the iterative method provides clarity. Want more? Try LeetCode 246: Strobogrammatic Number or LeetCode 248: Strobogrammatic Number III. Ready to flip? Head to Solve LeetCode 247 on LeetCode and generate those numbers today!