# Question

Formatted question description: https://leetcode.ca/all/248.html

 248	Strobogrammatic Number III

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.

Example:

Input: low = "50", high = "100"
Output: 3
Explanation: 69, 88, and 96 are three strobogrammatic numbers.

Note:
Because the range might be a large number, the lowand high numbers are represented as string.



# Algorithm

Goal is to get the number of symmetry numbers in a given range.

Initialize the cases of n=0 and n=1, and then recurse based on them.

The recursion length len is traversed from low to high, and then see if the current word length reaches len,

• If it is reached, first remove the multiple digits that start with 0,
• Then remove the numbers with the same length as low but less than low, and numbers with the same length as high but greater than high,
• Then the result is incremented by 1,
• Then add the five pairs of symmetric numbers to the left and right of the current word, and continue to call recursively

# Code

Java

• 
public class Strobogrammatic_Number_III {

public static void main(String[] args) {
Strobogrammatic_Number_III out = new Strobogrammatic_Number_III();
Solution s = out.new Solution();
System.out.println(s.strobogrammaticInRange("50", "100"));
}

public class Solution {

int res = 0;

public int strobogrammaticInRange(String low, String high) {

if (low == null || high == null) {
return res;
}

for (int i = low.length(); i <= high.length(); ++i) {
dfs(low, high, "", i);
dfs(low, high, "0", i);
dfs(low, high, "1", i);
dfs(low, high, "8", i);
}
return res;
}

void dfs(String low, String high, String path, int len) {
if (path.length() >= len) {

if (path.length() != len || (len != 1 && path.charAt(0) == '0')) {
return;
}

if ((len == low.length() && path.compareTo(low) < 0) || (len == high.length() && path.compareTo(high) > 0)) {
return;
}

++res;
}

dfs(low, high, "0" + path + "0", len);
dfs(low, high, "1" + path + "1", len);
dfs(low, high, "6" + path + "9", len);
dfs(low, high, "8" + path + "8", len);
dfs(low, high, "9" + path + "6", len);
}
}
}

• Todo

• class Solution(object):
def findStrobogrammatic(self, n):
"""
:type n: int
:rtype: List[str]
"""
self.d = {"0": "0", "1": "1", "6": "9", "8": "8", "9": "6"}

def dfs(half, path, n):
if len(path) == half:
pathStr = "".join(path)
if half * 2 == n:
toAppend = pathStr + "".join([self.d[x] for x in pathStr[::-1]])
toAppendInt = int(toAppend)
if self.low <= toAppendInt <= self.high:
self.count += 1
else:
for c in "018":
toAppend = pathStr + c + "".join([self.d[x] for x in pathStr[::-1]])
toAppendInt = int(toAppend)
if self.low <= toAppendInt <= self.high:
self.count += 1
return

for c in "01689":
if c == "0" and len(path) == 0:
continue
path.append(c)
dfs(half, path, n)
path.pop()

res = []
dfs(n / 2, [], n)
return res

def strobogrammaticInRange(self, low, high):
"""
:type low: str
:type high: str
:rtype: int
"""
if int(low) > int(high):
return 0
self.count = 0
self.low = int(low)
self.high = int(high)
for length in range(len(low), len(high) + 1):
self.findStrobogrammatic(length)
return self.count