Python 46ms 96.77% without generating all the numbers

• ``````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``````

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

It doesn't pass this

• Thanks man. Fixed.

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