# Fast general solution with detailed solution without generating numbers

• ### 1. Introduction

The idea based on this post. I rewrote some part of the codes and made it more general and understandable to all the language coding member. The main idea is as follow:

1. count the number less than high.
2. count the number less than low-1.
3. minus the two result getting the final answer.

### 2. Count the strobogrammatic number less than a number

We can divide the problem into two mini issues.

1. Count the number with the less length than the target string number.
2. Count the number with the same length of the target string number.

#### 2.1 With less length

To solve this problem, we can use dynamic programming. We know the following transfer equation:
`dp[0]=1 dp[1]=3,dp[2]=5 dp[i]=dp[i-2]*5`
It's simple to get the results. However, the results contain the first digital with `0`. To get rid of these invalid results, we only need times`4/5` since the are `5` in `dp[2]`.

#### 2.2 With the same length

It's the core and hard part of this problem. We need to take consideration of the total length and the situation equal to the target number.
Using one pointer `spos` to locate the candidate numbers and another length iteration pointer `pstr`. Every iteration the total length minus `2` since we get rid of the fist and last characters. For the candidates, there are three situations:

• Only one digital, it's `(0,1,8)`
• The first layer means the first pair, it's could be `(1,6,8,9)`
• The others could be `(0, 1, 6, 8, 9)`

For all the numbers in candidates,

1. if the number less than the target position number, we can directly add the `dp[pstr-2]`.
2. If it equals, we need to do more work. Checking the mapping position number is less than or equal to the target, record the count of this situations. If only reaches the half length of the numbers, it could be the right candidates. For example: the target number is `8 9 7 8 9`, the fist candidate number is `8` and the second is `9`, since the `8<9` and '6<8' , we reaches the most inner layer of the number, so `8 9 * 6 8` is the candidates (* means less than 7).

The coding could be like this:

``````class Solution(object):
def __init__(self):
# 1-{0,1,8} 2-{00,11,69,88,96}
self.cntmemo = {-1: 1, 0: 1, 1: 3, 2: 5}
# mapping the corresponding number
self.mapping = {0: 0, 1: 1, 6: 9, 8: 8, 9: 6}

def count_same_len(self, str_num):
slen = len(str_num)
spos, pstr = 0, slen
rescnt = 0
# record equal cnt when compare with the target
lesscnt = 0
while pstr > 0:
if slen == 1 or pstr == 1:
candidates = (0, 1, 8)
# first digital get rid of 0
elif pstr == slen:
candidates = (1, 6, 8, 9)
else:
candidates = (0, 1, 6, 8, 9)
for num in candidates:
# if the number less than the target,add all the possible in strlen-2
if num < int(str_num[spos]):
rescnt += self.cntmemo[pstr - 2]
# if equal we need to record, util to the middle compare
elif num == int(str_num[spos]):
# if the mapping pos num less or equal to the target, it's possible
if self.mapping[num] <= int(str_num[slen-1-spos]):
# record the less cnt
lesscnt += 1
if pstr < 3 and lesscnt == (slen + 1) / 2:
rescnt += 1
break
else:
return rescnt
pstr -= 2
spos += 1
return rescnt

def count_less_than(self, str_num):
rescnt, slen = 0, len(str_num)
# count the number less than str_num with length less than str len
if int(str_num) < 0: return 0
if slen > 1:
# len==1
rescnt = 3
# len>2
for i in xrange(2, slen):
rescnt += self.cntmemo[i] * 4 / 5
# plus the number with the same length
return rescnt+self.count_same_len(str_num)

def strobogrammaticInRange(self, low, high):
if int(low) > int(high):
return 0
# count all larger than 2
for i in xrange(3, len(high)):
self.cntmemo[i] = self.cntmemo[i - 2] * 5
return self.count_less_than(high) - self.count_less_than(str(int(low)-1))
``````

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