LeetCode Solutions Blog

Strobogrammatic Number III

Number: 248

Difficulty: Hard

Paid? Yes

Companies: N/A

Problem Description

Given two strings low and high representing the lower and upper bounds (inclusive) of an integer range, count the number of strobogrammatic numbers within that range. A strobogrammatic number appears the same when rotated 180 degrees.

Key Insights

Use recursion/backtracking to generate potential strobogrammatic numbers for each target length.
Only the pairs ('0','0'), ('1','1'), ('6','9'), ('8','8'), and ('9','6') can form valid strobogrammatic numbers.
Handle edge cases: for multi-digit numbers, a number cannot start with '0'.
Use string comparison to efficiently check whether a generated number falls within the bounds provided.
Process lengths from the length of low to the length of high.

Space and Time Complexity

Time Complexity: O(5^(N/2)) in the worst-case per length, where N is the target length, summed across all relevant lengths. Space Complexity: O(N) due to the recursion depth and auxiliary storage for each candidate number.

Solution

We apply a recursive DFS/backtracking approach to build numbers from the outside in, ensuring that pairs of digits are strobogrammatic. For even lengths, we fill the number symmetrically, while for odd lengths we choose one of '0', '1', or '8' for the middle digit. Each candidate number is then validated against the input range using string comparison (after ensuring it does not have an invalid leading zero). We sum the counts of valid candidates across all lengths from len(low) to len(high).

Code Solutions

# Python solution for Strobogrammatic Number III

class Solution:
    def strobogrammaticInRange(self, low: str, high: str) -> int:
        self.count = 0
        # Allowed strobogrammatic digit pairs
        pairs = [('0','0'), ('1','1'), ('6','9'), ('8','8'), ('9','6')]
        
        # Helper function to recursively build the number
        def dfs(n, currLen, num):
            # Completed a candidate number
            if currLen == 0:
                candidate = "".join(num)
                # Validate: avoid leading zeros (unless single digit) and ensure candidate is in range
                if (len(candidate) == 1 or candidate[0] != '0') and \
                   (len(candidate) > len(low) or candidate >= low) and \
                   (len(candidate) < len(high) or candidate <= high):
                    self.count += 1
                return
            # Special case: filling the middle digit in an odd-length candidate
            if currLen == 1:
                for mid in ['0', '1', '8']:
                    num[len(num)//2] = mid
                    candidate = "".join(num)
                    if (len(candidate) == 1 or candidate[0] != '0') and \
                       (len(candidate) > len(low) or candidate >= low) and \
                       (len(candidate) < len(high) or candidate <= high):
                        self.count += 1
                return
            # Place strobogrammatic pairs at symmetric positions
            for a, b in pairs:
                # Avoid numbers with a leading zero (if length > 1)
                if currLen == n and a == '0':
                    continue
                num[(n - currLen)] = a
                num[currLen - 1] = b
                dfs(n, currLen - 2, num)
        
        # Process each possible number length between len(low) and len(high)
        for length in range(len(low), len(high) + 1):
            num = [''] * length
            dfs(length, length, num)
        return self.count

# Example usage
solution = Solution()
print(solution.strobogrammaticInRange("50", "100"))  # Expected output: 3