# Python solution 180ms

• The solution is also base on strobogrammatic number II, but with a little optimization.

``````class Solution:
# @param {string} low
# @param {string} high
# @return {integer}
def strobogrammaticInRange(self, low, high):
a=self.below(high)
b=self.below(low,include=False)
return a-b if a>b else 0

'''
get how many strobogrammatic numbers less than n
'''
def below(self,n,include=True):
res=0
for i in range(1,len(n)):
res+=self.number(i)
l=self.strobogrammatic(len(n))
'''
'''
if include:
l=[num for num in l if (len(num)==1 or num[0]!='0') and num<=n]
else:
l=[num for num in l if (len(num)==1 or num[0]!='0') and num<n]
return res+len(l)

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

'''
get number of strobogrammatic numbers of length l
'''
def number(self,l):
if l==0:
return 0
'''
If l is an even number, the first digit has four choices (1,6,8,9). digits
at other position have five choices(0,1,6,8,9)
'''
if l%2==0:
return 4*(5**(l/2-1))
'''
If l is an odd number, the first digit has four choices (1,6,8,9) and digit
at the middle has 3 choices (0,1,8),other digits have 5 choices.
digit at other position could be 0,1,6,8,9
'''
elif l==1:
return 3
else:
return 3*(5**(l/2-1))*4``````

• Hi, yang.zheng.904. Could you please give some explanations for your function `number`?

• Hi, jianchao, I have added explanations to that function.

• Hi, yang.zheng.904. Thank you for your nice explanations :-) I get it now.

BTW, translating this code into C++ directly gives the MLE...

• Nice solution and nice explanation, a little bit change to your solution:

``````def strobogrammaticInRange(self, low, high):
a, b = self.below(high), self.below(low, include=False)
return a -b if a > b else 0

def below(self, n, include=True):
res = 0
for i in xrange(1, len(n)):
res += self.number(i)
l = self.strobogrammatic(len(n))
if include:
tmp = [num for num in l if num <= n]
else:
tmp = [num for num in l if num < n]
return res + len(tmp)

def strobogrammatic(self, n):
return self.helper(n, n)

def helper(self, m, n):
if m == 0:
return [""]
if m == 1:
return ["0", "1", "8"]
l = self.helper(m-2, n)
res = []
for i in l:
if m != n:
res.append("0"+i+"0")
res.append("1"+i+"1")
res.append("6"+i+"9")
res.append("8"+i+"8")
res.append("9"+i+"6")
return res

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

• Great combination of recursive and math! That's brilliant!

• @caikehe

The code for generating `res` could be shorten like this

``````return [a + i + b for a, b in ['00', '11', '69', '88', '96'][m == n:] for i in l]
``````

• @tlhuang