class Solution:
def strobogrammaticInRange(self, low: str, high: str) -> int:
self.count = 0
pairs = [('0','0'), ('1','1'), ('6','9'), ('8','8'), ('9','6')]
def dfs(s, length):
if len(s) > len(high) or (len(s) > 1 and s[0] == '0'):
return
if len(s) >= len(low) and len(s) <= len(high):
if (len(s) == len(low) and s < low) or (len(s) == len(high) and s > high):
pass
else:
if not (len(s) > 1 and s[0] == '0'):
self.count += 1
if len(s) + 2 > len(high):
return
for a, b in pairs:
dfs(a + s + b, length)
for length in range(len(low), len(high)+1):
if length == 1:
for c in ['0','1','8']:
if (len(low) == 1 and c < low) or (len(high) == 1 and c > high):
continue
self.count += 1
else:
for a, b in pairs:
if a == '0':
continue
dfs(a + b, length)
return self.count
class Solution {
public:
int strobogrammaticInRange(string low, string high) {
int count = 0;
vector<pair<char, char>> pairs = {{'0','0'}, {'1','1'}, {'6','9'}, {'8','8'}, {'9','6'}};
function<void(string, int)> dfs = [&](string s, int length) {
if (s.length() > high.length() || (s.length() > 1 && s[0] == '0'))
return;
if (s.length() >= low.length() && s.length() <= high.length()) {
if ((s.length() == low.length() && s < low) || (s.length() == high.length() && s > high)) {
// do nothing
} else {
if (!(s.length() > 1 && s[0] == '0'))
count++;
}
}
if (s.length() + 2 > high.length()) return;
for (auto &p : pairs) {
dfs(p.first + s + p.second, length);
}
};
for (int length = low.length(); length <= high.length(); ++length) {
if (length == 1) {
for (char c : {'0','1','8'}) {
if ((low.length() == 1 && c < low[0]) || (high.length() == 1 && c > high[0]))
continue;
count++;
}
} else {
for (auto &p : pairs) {
if (p.first == '0') continue;
dfs(string(1, p.first) + string(1, p.second), length);
}
}
}
return count;
}
};
class Solution {
private int count = 0;
private final char[][] pairs = {{'0','0'}, {'1','1'}, {'6','9'}, {'8','8'}, {'9','6'}};
public int strobogrammaticInRange(String low, String high) {
for (int length = low.length(); length <= high.length(); length++) {
if (length == 1) {
for (char c : new char[]{'0','1','8'}) {
if ((low.length() == 1 && c < low.charAt(0)) || (high.length() == 1 && c > high.charAt(0)))
continue;
count++;
}
} else {
for (char[] p : pairs) {
if (p[0] == '0') continue;
dfs(new StringBuilder().append(p[0]).append(p[1]).toString(), length, low, high);
}
}
}
return count;
}
private void dfs(String s, int length, String low, String high) {
if (s.length() > high.length() || (s.length() > 1 && s.charAt(0) == '0'))
return;
if (s.length() >= low.length() && s.length() <= high.length()) {
if ((s.length() == low.length() && s.compareTo(low) < 0) || (s.length() == high.length() && s.compareTo(high) > 0)) {
// do nothing
} else {
if (!(s.length() > 1 && s.charAt(0) == '0'))
count++;
}
}
if (s.length() + 2 > high.length()) return;
for (char[] p : pairs) {
dfs(p[0] + s + p[1], length, low, high);
}
}
}
var strobogrammaticInRange = function(low, high) {
let count = 0;
const pairs = [['0','0'], ['1','1'], ['6','9'], ['8','8'], ['9','6']];
function dfs(s, length) {
if (s.length > high.length || (s.length > 1 && s[0] === '0')) return;
if (s.length >= low.length && s.length <= high.length) {
if ((s.length === low.length && s < low) || (s.length === high.length && s > high)) {
// do nothing
} else {
if (!(s.length > 1 && s[0] === '0')) count++;
}
}
if (s.length + 2 > high.length) return;
for (const [a, b] of pairs) {
dfs(a + s + b, length);
}
}
for (let length = low.length; length <= high.length; length++) {
if (length === 1) {
for (const c of ['0','1','8']) {
if ((low.length === 1 && c < low) || (high.length === 1 && c > high)) continue;
count++;
}
} else {
for (const [a, b] of pairs) {
if (a === '0') continue;
dfs(a + b, length);
}
}
}
return count;
};
The Leetcode problem "Strobogrammatic Number III" asks you to count how many numbers in a given range are strobogrammatic. A strobogrammatic number is a number that looks the same when rotated 180 degrees (turned upside down). For example, 69 becomes 96, 88 remains 88, and 818 remains 818 after rotation.
You are given two strings low and high that represent the lower and upper bounds of the range (inclusive). Your task is to find how many strobogrammatic numbers exist in this range.
low and high are non-negative integers represented as strings, and may be very large (up to 15 digits).low, high].To solve this problem, let's first understand what a strobogrammatic number is. Only certain digits are valid in a strobogrammatic number: 0, 1, 6, 8, 9. When flipped, these digits either remain the same or become another valid digit (e.g., 6 becomes 9 and vice versa).
A brute-force approach would be to check every number between low and high and determine if each is strobogrammatic. However, since the range can be very large (up to 1015), this is not feasible.
Instead, we can generate all strobogrammatic numbers whose lengths are between the lengths of low and high, and count only those that fall within the given range. This avoids unnecessary checks and leverages the special structure of strobogrammatic numbers.
The core idea is to use recursive generation (depth-first search) to construct all strobogrammatic numbers of valid lengths, and count only those within the specified range.
low, high].len(low) to len(high), inclusive.
Example: low = "50", high = "100"
Brute-force Approach: Checking every number between low and high would take O(N) time, where N is the size of the range, which is infeasible for large ranges (up to 1015).
Optimized Approach: The recursive method generates only strobogrammatic numbers. For each possible length, the number of candidates is O(5n/2), where n is the number length (since there are 5 pairs). For each candidate, comparison to bounds is O(n), but the total number of candidates is much smaller than the size of the range.
Space Complexity: The space is mainly used by the recursion stack, which is O(n) for the maximum length, and by storing temporary strings.
The key insight for "Strobogrammatic Number III" is to avoid brute-force enumeration by generating only valid strobogrammatic numbers of relevant lengths, and counting those within the range. We use recursion to build numbers from the inside out, leveraging the symmetry of strobogrammatic pairs. This approach is both efficient and elegant, allowing us to handle very large ranges without performance issues.