Description
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 <= 15low and high consist of only digits.low <= highlow and high do not contain any leading zeros except for zero itself.
Solutions
Solution 1: Recursion
If the length is 1, then the strobogrammatic numbers are only 0, 1, 8; if the length is 2, then the strobogrammatic numbers are only 11, 69, 88, 96.
We design a recursive function dfs(u), which returns the strobogrammatic numbers of length u.
If u is 0, return a list containing an empty string, i.e., [""]; if u is 1, return the list ["0", "1", "8"].
If u is greater than 1, we traverse all the strobogrammatic numbers of length u - 2. For each strobogrammatic number v, we add 1, 8, 6, 9 to both sides of it, and we can get the strobogrammatic numbers of length u.
Note that if u ≠ n, we can also add 0 to both sides of the strobogrammatic number.
Let the lengths of low and high be a and b respectively.
Next, we traverse all lengths in the range [a,..b]. For each length n, we get all strobogrammatic numbers dfs(n), and then check whether they are in the range [low, high]. If they are, we increment the answer.
The time complexity is O(2^{n+2} × log n).
Similar problems:
PythonJavaC++Go
class Solution:
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):
if low <= int(s) <= high:
ans += 1
return ans(code-box)
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) {
ans.add(p[0] + v + p[1]);
}
if (u != n) {
ans.add(0 + v + 0);
}
}
return ans;
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
