## 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 low and high numbers are represented as string.

## Rust Solution

``````struct Solution;

impl Solution {
fn strobogrammatic_in_range(low: String, high: String) -> i32 {
let mut res = 0;
let low: Vec<char> = low.chars().collect();
let high: Vec<char> = high.chars().collect();
for size in low.len()..=high.len() {
let mut cur = vec!['0'; size];
Self::dfs(size, 0, &mut cur, &mut res, &low, &high);
}
res
}

fn dfs(
size: usize,
start: usize,
cur: &mut Vec<char>,
all: &mut i32,
low: &[char],
high: &[char],
) {
if start >= (1 + size) / 2 {
if size > 1 && cur == '0' {
return;
}
if size == low.len() && cur.as_slice() < low {
return;
}
if size == high.len() && cur.as_slice() > high {
return;
}
*all += 1;
} else {
if start == size - 1 - start {
for &c in &['0', '1', '8'] {
cur[start] = c;
Self::dfs(size, start + 1, cur, all, low, high);
}
} else {
for &(a, b) in &[('0', '0'), ('1', '1'), ('6', '9'), ('8', '8'), ('9', '6')] {
cur[start] = a;
cur[size - 1 - start] = b;
Self::dfs(size, start + 1, cur, all, low, high);
}
}
}
}
}

#[test]
fn test() {
let low = "50".to_string();
let high = "100".to_string();
let res = 3;
assert_eq!(Solution::strobogrammatic_in_range(low, high), res);
let low = "0".to_string();
let high = "0".to_string();
let res = 1;
assert_eq!(Solution::strobogrammatic_in_range(low, high), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.