LeetCode 248: Strobogrammatic Number III Solution in Python – A Step-by-Step Guide

What Is LeetCode 248: Strobogrammatic Number III?

In LeetCode 248: Strobogrammatic Number III, you’re given two strings, low and high, representing a range of numbers, and your task is to count how many strobogrammatic numbers (those that look the same when rotated 180 degrees) lie within that range, inclusive. This extends LeetCode 247 by adding range constraints, requiring careful handling of lengths and comparisons.

Problem Statement

• Input: Two strings low and high defining a range.
• Output: An integer—count of strobogrammatic numbers from low to high (inclusive).
• Rules: Valid digits are 0, 1, 6, 8, 9; 6 rotates to 9, 9 to 6, 0, 1, 8 stay the same; numbers must match length and value constraints.

Constraints

• low.length and high.length: 1 to 15.
• low <= high.
• Strings contain digits 0-9, no leading zeros unless the number is "0".

Examples

• Input: low = "50", high = "100"
• Output: 3 (strobogrammatic: "69", "88", "96").
• Input: low = "0", high = "0"
• Output: 1 ("0" is strobogrammatic).
• Input: low = "1", high = "10"
• Output: 2 ("1", "8").

Understanding the Problem: Counting in a Range

To solve LeetCode 248: Strobogrammatic Number III in Python, we need to count strobogrammatic numbers between low and high. A strobogrammatic number uses:

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

We must generate numbers of lengths from low.length to high.length and filter those within the range, avoiding leading zeros except for "0". We’ll use two methods: 1. Best Solution (Backtracking with Bounds): O(5^(n/2)) time—efficient and precise. 2. Alternative Solution (Iterative with Filtering): O(5^(n/2)) time—simpler but less optimized.

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

Best Solution: Backtracking with Bounds Checking

Why This Is the Best Solution

The backtracking approach is the top choice for LeetCode 248 because it generates strobogrammatic numbers efficiently while checking bounds on the fly, avoiding unnecessary computations. It builds numbers symmetrically and counts only those within low to high, making it both fast and accurate.

How It Works

Picture this solution as building a number layer by layer, like stacking blocks, but only keeping the stack if it fits between a lower shelf (low) and an upper shelf (high). You start from the outside edges and work inward, ensuring each number is strobogrammatic and within bounds. Here’s how it works, step-by-step, explained simply:

• Base Idea: A strobogrammatic number is symmetric (e.g., "1881" or "181"). We use pairs (0-0, 1-1, 6-9, 8-8, 9-6) and middle digits (0, 1, 8) for odd lengths.
• Backtracking Process:
• Generate numbers of length n (from low.length to high.length).
• Use two pointers: left and right, adding pairs from the outside in.
• For each length, count numbers where low <= num <= high.
• Bounds Checking:
• Compare strings lexicographically (e.g., "50" < "69" < "100").
• Skip numbers with leading zeros unless n = 1 and it’s "0".
• Helper Function: Recursively build numbers and count those in range.

Step-by-Step Example

Example: low = "50", high = "100"

• Lengths: 2 (low) to 3 (high).
• Length 2:
• Pairs: (1, 1), (6, 9), (8, 8), (9, 6)—no (0, 0) due to leading zero.
• Generate:
• "11" → < "50", skip.
• "69" → "50" ≤ "69" ≤ "100", count +1.
• "88" → "50" ≤ "88" ≤ "100", count +1.
• "96" → "50" ≤ "96" ≤ "100", count +1.
• Length 3:
• Outer: (1, 1), (6, 9), (8, 8), (9, 6).
• Middle: 0, 1, 8.
• Check:
• "101" > "100", skip.
• "111" > "100", skip.
• "181" > "100", skip.
• "609" > "100", skip.
• (and so on—all exceed "100").
• Result: Count = 3 ("69", "88", "96").

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

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

        # Step 2: Helper function to build and count
        def count_numbers(length, low, high):
            if length == 0:
                return [""]
            if length == 1:
                return ["0", "1", "8"]

            # Build inner numbers
            inner = count_numbers(length - 2, low, high)
            result = []
            for left_digit, right_digit in pairs:
                # Skip leading zero for full length unless n=1
                if left_digit == '0' and length == len(low) and length > 1:
                    continue
                for num in inner:
                    candidate = left_digit + num + right_digit
                    # Only include if within bounds
                    if (len(candidate) == len(low) and candidate < low) or \
                       (len(candidate) == len(high) and candidate > high):
                        continue
                    result.append(candidate)
            return result

        # Step 3: Count for each length
        low_len, high_len = len(low), len(high)
        count = 0

        # Step 4: Iterate through possible lengths
        for n in range(low_len, high_len + 1):
            candidates = count_numbers(n, low, high)
            for num in candidates:
                # Double-check bounds (for edge cases)
                if (n == low_len and num < low) or (n == high_len and num > high):
                    continue
                count += 1

        # Step 5: Return total count
        return count

• Time Complexity O(5^(n/2)): Exponential—generating all strobogrammatic numbers up to max length.
• Space Complexity: O(5^(n/2))—storing candidates.

This method is like a number factory with a quality check—it’s efficient once you understand it!

Alternative Solution: Iterative with Filtering

Why an Alternative Approach?

The iterative approach generates all strobogrammatic numbers for each length and then filters them against the range. It’s less efficient but easier to follow step-by-step, making it a good starting point for beginners.

How It Works

• Generate all strobogrammatic numbers iteratively from length low.length to high.length.
• Filter each number to check if it’s within low to high.

Step-by-Step Example

Example: low = "50", high = "100"

• Length 2:
• Generate: "11", "69", "88", "96".
• Filter: "50" ≤ "69", "88", "96" ≤ "100" → 3 numbers.
• Length 3:
• Generate: "101", "111", "181", "609", etc.
• Filter: All > "100" → 0 numbers.
• Result: Count = 3.

Code for Iterative Approach

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

        # Step 2: Build all numbers iteratively
        def generate_numbers(n):
            if n == 1:
                return ["0", "1", "8"]
            if n == 0:
                return [""]
            result = [""]
            for length in range(2, n + 1, 2):
                new_result = []
                for num in result:
                    for l, r in pairs:
                        if l == '0' and length == n:
                            continue
                        new_result.append(l + num + r)
                result = new_result
            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

        # Step 3: Count within range
        count = 0
        low_len, high_len = len(low), len(high)
        for n in range(low_len, high_len + 1):
            numbers = generate_numbers(n)
            for num in numbers:
                if (n == low_len and num < low) or (n == high_len and num > high):
                    continue
                count += 1

        return count

• Time Complexity: O(5^(n/2))—generating all numbers.
• Space Complexity: O(5^(n/2))—storing all numbers.

It’s straightforward but less optimized.

Comparing the Two Solutions

• Best Solution (Backtracking):
• Pros: Efficient bounds checking, O(5^(n/2)) time.
• Cons: Recursion might be tricky.
• Alternative Solution (Iterative):
• Pros: Linear flow, easy to debug.
• Cons: Generates extra numbers, less efficient.

Backtracking wins for precision.

Additional Examples and Edge Cases

Single Digit

• low = "0", high = "1" → 2 ("0", "1").

Same Length

• low = "10", high = "20" → 1 ("11").

Wide Range

• low = "1", high = "1000" → counts across lengths.

Both handle these well.

Complexity Breakdown

• Backtracking:
• Time: O(5^(n/2))—filtered generation.
• Space: O(5^(n/2))—candidates.
• Iterative:
• Time: O(5^(n/2))—full generation.
• Space: O(5^(n/2))—all numbers.

Backtracking is leaner.

Key Takeaways for Beginners

• Backtracking: Build and check simultaneously.
• Bounds: Use string comparison for ranges.
• Iterative: Generate then filter—simpler flow.
• Python Tip: Strings compare easily—see [Python Basics](/python/basics).

Final Thoughts: Count Flippable Numbers Like a Pro

LeetCode 248: Strobogrammatic Number III in Python is a rewarding range-counting challenge. The backtracking solution offers efficiency, while the iterative method provides clarity. Want more? Try LeetCode 246: Strobogrammatic Number or LeetCode 247: Strobogrammatic Number II. Ready to count? Head to Solve LeetCode 248 on LeetCode and tally those numbers today!