Strobogrammatic Number III

Problem: Strobogrammatic Number III

To get count of strobogrammatic numbers in range a to b, we simply get count of numbers in range 0 to a and range 0 to b to get the answer. To get count of strobogrammatic numbers smaller than a, we can first count strobogrammatic numbers shorter than a, then we generate all strobogrammatic numbers as longs as a and find how many are smaller than a.

Code in Python:

class Solution(object):
    def strobogrammaticInRange(self, low, high):
        """
        :type low: str
        :type high: str
        :rtype: int
        """
        if int(low) > int(high): return 0
        if low != "0":
            return self.strobogrammaticInRange("0", high) - self.strobogrammaticInRange("0", str(int(low)-1))
        res = 0
        for i in xrange(1, len(high)):
            res += self.count(i)
        nums = self.strobogrammatic(len(high))
        nums = [num for num in nums if (len(num)==1 or num[0] != '0') and num <= high]
        return res+len(nums)

    def strobogrammatic(self, length):
        res = []
        if length == 1: return ['0', '1', '8']
        if length == 2: return ['00', '11', '69', '88', '96']
        for num in self.strobogrammatic(length-2):
            res.append('0'+num+'0')
            res.append('1'+num+'1')
            res.append('6'+num+'9')
            res.append('8'+num+'8')
            res.append('9'+num+'6')
        return res

    def count(self, length):
        if length == 0: return 0
        if length % 2 == 0: return 4*(5**(length/2-1))
        elif length == 1: return 3
        else: return 3*(5**(length/2-1))*4