Strobogrammatic Number III
题目描述
解题方法
利用2的方法，再加上对于其他长度的概率计算，可以得出结果。
Solution
class Solution(object):
s_map = {
"0":"0",
"1":"1",
"8":"8"
}
d_map = {
"0":"0",
"1":"1",
"6":"9",
"8":"8",
"9":"6"
}
def strobogrammaticInRange(self, low, high):
"""
:type low: str
:type high: str
:rtype: int
"""
a = self.below(high)
b = self.below(low, include=False)
return a - b if a > b else 0
def below(self, n, include=True):
"""
get how many strobogrammatic numbers less than n
"""
res = 0
for i in range(1, len(n)):
res += self.number(i)
l = self.findStrobogrammatic(len(n))
if include:
l = [num for num in l if num <= n]
else:
l = [num for num in l if num < n]
return res + len(l)
def number(self, l):
if l == 0:
return 0
if l == 1:
return 3
if l % 2 == 0:
return 4 * (5**(l/2-1))
else:
return 4 * (5**(l/2-1)) * 3
def findStrobogrammatic(self, n):
"""
:type n: int
:rtype: List[str]
"""
if not n:
return []
if n == 1:
return ["0", "1", "8"]
if n == 2:
return ["11","69","88","96"]
result = []
self.findHelper(result, "", "", 1, n)
return result
def findHelper(self, result, left_str, right_str, start, end):
if start == end: # only one character left
for c in self.s_map:
new_str = left_str + c + right_str
result.append(new_str)
return
elif start + 1 == end:
for c in self.d_map:
new_str = left_str + c + self.d_map[c] + right_str
result.append(new_str)
return
# start and end
for c in self.d_map:
if start == 1 and c == "0":
continue
left_str += c
right_str = self.d_map[c] + right_str
self.findHelper(result, left_str, right_str, start+1, end-1)
left_str = left_str[:-1]
right_str = right_str[1:]