# Question

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

Given two strings low and high that represent two integers low and high where low <= high, return the number of strobogrammatic numbers in the range [low, high].

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

Example 1:

Input: low = "50", high = "100"
Output: 3


Example 2:

Input: low = "0", high = "0"
Output: 1


Constraints:

• 1 <= low.length, high.length <= 15
• low and high consist of only digits.
• low <= high
• low and high do not contain any leading zeros except for zero itself.

# Algorithm

The objective is to determine the count of symmetric numbers within a specified range.

Begin by establishing base cases for n=0 and n=1, and proceed with recursive calls based on these cases.

During the recursion, iterate from the lower to the upper limit of the range, examining if the current word length matches the target length, len:

• Upon reaching the target length, initially eliminate numbers that begin with multiple zeros.
• Next, exclude numbers that are of the same length as the lower limit but smaller, and numbers of the same length as the upper limit but larger.
• Subsequently, increment the result count by 1.
• Finally, append the five pairs of symmetric digits to both ends of the current word and continue with the recursive process.

# Code

• 
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);
}
}
}

############

class Solution {
private static final int[][] PAIRS = { {1, 1}, {8, 8}, {6, 9}, {9, 6}};
private int n;

public int strobogrammaticInRange(String low, String high) {
int a = low.length(), b = high.length();
long l = Long.parseLong(low), r = Long.parseLong(high);
int ans = 0;
for (n = a; n <= b; ++n) {
for (String s : dfs(n)) {
long v = Long.parseLong(s);
if (l <= v && v <= r) {
++ans;
}
}
}
return ans;
}

private List<String> dfs(int u) {
if (u == 0) {
return Collections.singletonList("");
}
if (u == 1) {
return Arrays.asList("0", "1", "8");
}
List<String> ans = new ArrayList<>();
for (String v : dfs(u - 2)) {
for (var p : PAIRS) {
}
if (u != n) {
}
}
return ans;
}
}

• using ll = long long;

class Solution {
public:
const vector<pair<char, char>> pairs = { {'1', '1'}, {'8', '8'}, {'6', '9'}, {'9', '6'} };

int strobogrammaticInRange(string low, string high) {
int n;
function<vector<string>(int)> dfs = [&](int u) {
if (u == 0) return vector<string>{""};
if (u == 1) return vector<string>{"0", "1", "8"};
vector<string> ans;
for (auto& v : dfs(u - 2)) {
for (auto& [l, r] : pairs) ans.push_back(l + v + r);
if (u != n) ans.push_back('0' + v + '0');
}
return ans;
};

int a = low.size(), b = high.size();
int ans = 0;
ll l = stoll(low), r = stoll(high);
for (n = a; n <= b; ++n) {
for (auto& s : dfs(n)) {
ll v = stoll(s);
if (l <= v && v <= r) {
++ans;
}
}
}
return ans;
}
};

• '''
>>> 'abc' < 'def'
True
>>> 'abc' < 'aef'
True
>>> 'abc' < 'aaf'
False
'''
class Solution:
def strobogrammaticInRange(self, low: str, high: str) -> int:
self.count = 0
self.low, self.high = low, high
self.dfs('')
self.dfs('0')
self.dfs('1')
self.dfs('8')
return self.count

def dfs(self, s):
if len(s) >= len(self.low) and len(s) <= len(self.high):
if (len(s) == len(self.low) and s < self.low) or (len(s) == len(self.high) and s > self.high):
return
if not (len(s) > 1 and s[0] == '0'):
self.count += 1
if len(s) + 2 > len(self.high):
# because next step is append 2 chars at beginning and end
return
self.dfs('0' + s + '0')
self.dfs('1' + s + '1')
self.dfs('6' + s + '9')
self.dfs('8' + s + '8')
self.dfs('9' + s + '6')

############

class Solution: # no trim, just check if low <= int(s) <= high
def strobogrammaticInRange(self, low: str, high: str) -> int:
def dfs(u):
if u == 0:
return ['']
if u == 1:
return ['0', '1', '8']
ans = []
for v in dfs(u - 2):
for l, r in ('11', '88', '69', '96'):
ans.append(l + v + r)
if u != n:
ans.append('0' + v + '0')
return ans

a, b = len(low), len(high)
low, high = int(low), int(high)
ans = 0
for n in range(a, b + 1):
for s in dfs(n): # so basically no trimming applied in dfs(), just get all
if low <= int(s) <= high:
ans += 1
return ans

############

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


• func strobogrammaticInRange(low string, high string) int {
n := 0
var dfs func(int) []string
dfs = func(u int) []string {
if u == 0 {
return []string{""}
}
if u == 1 {
return []string{"0", "1", "8"}
}
var ans []string
pairs := [][]string{ {"1", "1"}, {"8", "8"}, {"6", "9"}, {"9", "6"} }
for _, v := range dfs(u - 2) {
for _, p := range pairs {
ans = append(ans, p[0]+v+p[1])
}
if u != n {
ans = append(ans, "0"+v+"0")
}
}
return ans
}
a, b := len(low), len(high)
l, _ := strconv.Atoi(low)
r, _ := strconv.Atoi(high)
ans := 0
for n = a; n <= b; n++ {
for _, s := range dfs(n) {
v, _ := strconv.Atoi(s)
if l <= v && v <= r {
ans++
}
}
}
return ans
}