Problem statement

https://leetcode.com/problems/strobogrammatic-number-iii/

Solution

One solution is just to use problem 0247, because we do not have a lot of strobogrammatic numbers. Let us generate all of them with no more than number of digits high have and then just check how many of them lies inside given range.

Complexity

It is $\mathcal{O}(5^{k/2})$, because we have asymptotically this number of strobogrammatic numbers. Space complexity is the same.

Code

class Solution:
    def findStrobogrammatic(self, n):
        d = {"0":"0", "1":"1", "6":"9", "8":"8", "9":"6"}
        
        def dfs(n):
            if n == 0: return [""]
            if n == 1: return ["0", "1", "8"]
            ans = []
            found = dfs(n - 2)
            for dig, s in product(d, found):
                ans.append(dig + s + d[dig])
            return ans
        
        return [i for i in dfs(n) if (i[0] != "0" or i == "0")]
    
    def strobogrammaticInRange(self, low, high):
        nums = []
        for i in range(1, len(high) + 1):
            nums.extend(self.findStrobogrammatic(i))
        return sum(int(low) <= int(num) <= int(high) for num in nums)

Remark

First, we actually need function to evaluate number of strobogrammatic number $\leqslant A$. They can be split into 3 groups:

  1. With lesser number of digits.
  2. Check number reconstructed from the first half, for example if $A = 16830$, we need to check number $16891$, and if $A= 6130$, to check $6119$.
  3. Find number of numbers for the first half, which have only desired symbols, for example for $16830$, find all $3$-digits numbers $<168$, such that each symbol is $0,1,6,8,9$ and the last one is $0,1,8$, if it is $6130$, find all $2$-digits numbers $<61$ with each symbol is $0,1,6,8,9$. All this is quite painful to code, but complexity is $O(k)$, where $k$ is length of number.