Strobogrammatic Number III Solution in Python

Explore More Solutions

Ah, the Strobogrammatic Number III problem! It’s like trying to find a number that looks the same when flipped upside down. Imagine you’re at a carnival, and you see a funhouse mirror that makes you look like a strobogrammatic number. You’re all twisted and turned, but somehow, you still look fabulous!

In the world of LeetCode, this problem is a delightful puzzle where you need to count how many numbers within a given range are strobogrammatic. A strobogrammatic number is one that appears the same when rotated 180 degrees. So, if you think your life is upside down, just wait until you see these numbers!

Problem Description

Given two strings low and high, representing the lower and upper bounds of a range, your task is to count how many strobogrammatic numbers exist within that range.

Code Solution


class Solution:
    def strobogrammaticInRange(self, low: str, high: str) -> int:
        pairs = [['0', '0'], ['1', '1'], ['6', '9'], ['8', '8'], ['9', '6']]
        ans = 0

        def dfs(s: list[str], l: int, r: int) -> None:
            nonlocal ans
            if l > r:
                if len(s) == len(low) and ''.join(s) < low:
                    return
                if len(s) == len(high) and ''.join(s) > high:
                    return
                ans += 1
                return

            for leftDigit, rightDigit in pairs:
                if l == r and leftDigit != rightDigit:
                    continue
                s[l] = leftDigit
                s[r] = rightDigit
                if len(s) > 1 and s[0] == '0':
                    continue
                dfs(s, l + 1, r - 1)

        for n in range(len(low), len(high) + 1):
            dfs([' '] * n, 0, n - 1)

        return ans

Approach Explanation

The code uses a depth-first search (DFS) approach to explore all possible strobogrammatic numbers within the specified range. It builds numbers by placing pairs of digits at both ends and checking if they fall within the bounds defined by low and high. The function ensures that no leading zeros are present unless the number is “0” itself.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(N * 5^(N/2)), where N is the length of the longest number in the range.
Space Complexity	O(N), which is used for the recursive stack and the temporary list to hold the digits.

Real-World Example

Imagine you’re at a digital clock store, and you want to find out how many clocks can display a strobogrammatic time. You’d be counting all the possible times that look the same when viewed upside down. Just like how you might count the number of times you’ve flipped your phone to check the time during a boring meeting!