straightforward python solution 300ms


  • 0
    N

    The idea is to store strobogrammatic numbers of length i in list result[i], including those starting with '0', because result[i+2] is dependent on result[i] and we would miss cases like '1001' if we don't include '00' in result[2].

    class Solution(object):
        def strobogrammaticInRange(self, low, high):
            """
            :type low: str
            :type high: str
            :rtype: int
            """
            lowD = len(low)
            highD = len(high)
            if int(low) > int(high):
                return 0
            result = [[''], ['1', '0', '8']]
            p = {'0':'0', '1':'1', '6':'9', '8':'8', '9':'6'}
            # generate strobogrammatic nums of length i
            for _i in range(2, highD+1):
                result.append([c + word + p[c] for c in p for word in result[_i-2]])
            count = 0
            # we have to not count those that start with '0'
            if lowD != highD:
                for word in result[lowD]:
                    if int(word) >= int(low):
                        count += 1
                for word in result[highD]:
                    if word[0] != '0' and int(word) <= int(high):
                        count += 1
            else:
                for word in result[lowD]:
                    if int(word) >= int(low) and int(word) <= int(high):
                        count += 1
            for _i in range(lowD+1, highD):
                for word in result[_i]:
                    if word[0] != '0':
                        count += 1
            return count
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.