Python 46ms 96.77% without generating all the numbers


  • 0
    W
    class Solution(object):
        def strobogrammaticInRange(self, low, high):
            """
            :type low: str
            :type high: str
            :rtype: int
            """  
            if int(low) > int(high):
                return 0
            memo = {-1:1, 0:1,
                    1:3, #["0","1","8"], 
                    2:5  #["00", "11", "69", "88", "96"]
                    }
            i = 2
            while i < len(high):
                i += 1
                memo[i] = memo[i-2] * 5
            return self.counter(high, memo) - self.counter(str(int(low)-1), memo)
            
        def counter(self, s, memo):
            rev = {1:1, 8:8, 6:9, 9:6, 0:0}
            if int(s) < 0:
                return 0
            if len(s) > 1:
                ans = 3 + sum([memo[i] for i in xrange(2,len(s))]) * 4 / 5
            else:
                ans = 0
            t, k, flag = 0, len(s), 0
            while k > 0:
                if len(s) == 1 or k == 1:
                    candidates = (0,1,8)     # single-digit numbers
                elif k == len(s):
                    candidates = (1,6,8,9)   # first digit of numbers longer than one digit
                else:
                    candidates = (0,1,6,8,9) # the rest of digits for numbers longer than one digit
                for i,d in enumerate(candidates):
                    if d < int(s[t]):
                        ans += memo[k-2]     # safe add
                    elif d == int(s[t]):
                        if rev[d] <= int(s[len(s)-t-1]):
                            flag += 1
                            if k < 3 and flag == (len(s)+1)/2:
                                ans += 1
                        break
                    else:
                        return ans
                k -= 2
                t += 1
            return ans

  • 0
    Z

    Run this test case: "100", "999".

    It doesn't pass this


  • 0
    W

    Thanks man. Fixed.


Log in to reply
 

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