# 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.

``````class Solution {
public:
int strobogrammaticInRange(string low, string high) {
int res = 0;
for (int i = low.size(); i <= high.size(); ++i) {
find(low, high, "", i, res);
find(low, high, "0", i, res);
find(low, high, "1", i, res);
find(low, high, "8", i, res);
}
return res;
}
void find(string low, string high, string path, int len, int &res) {
if (path.size() >= len) {
if (path.size() != len || (len != 1 && path[0] == '0')) return;
if ((len == low.size() && path.compare(low) < 0) || (len == high.size() && path.compare(high) > 0)) {
return;
}
++res;
}
find(low, high, "0" + path + "0", len, res);
find(low, high, "1" + path + "1", len, res);
find(low, high, "6" + path + "9", len, res);
find(low, high, "8" + path + "8", len, res);
find(low, high, "9" + path + "6", len, res);
}
};
``````

``````class Solution {
public:
int strobogrammaticInRange(string low, string high) {
int res = 0;
find(low, high, "", res);
find(low, high, "0", res);
find(low, high, "1", res);
find(low, high, "8", res);
return res;
}
void find(string low, string high, string w, int &res) {
if (w.size() >= low.size() && w.size() <= high.size()) {
if (w.size() == high.size() && w.compare(high) > 0) {
return;
}
if (!(w.size() > 1 && w[0] == '0') && !(w.size() == low.size() && w.compare(low) < 0)) {
++res;
}
}
if (w.size() + 2 > high.size()) return;
find(low, high, "0" + w + "0", res);
find(low, high, "1" + w + "1", res);
find(low, high, "6" + w + "9", res);
find(low, high, "8" + w + "8", res);
find(low, high, "9" + w + "6", res);
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/248

Strobogrammatic Number II

Strobogrammatic Number

https://leetcode.com/problems/strobogrammatic-number-iii/

https://leetcode.com/problems/strobogrammatic-number-iii/discuss/67431/My-Java-solution-easy-to-understand

https://leetcode.com/problems/strobogrammatic-number-iii/discuss/67406/Clear-Java-AC-solution-using-Strobogrammatic-Number-II-method

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation