# [LeetCode] Strobogrammatic Number III

The idea is similar to Strobogrammatic Number II: generate all those in-range strobogrammatic numbers and count.

You may refer to this link for a very readable code, which I have rewritten in C++ below.

 1 class Solution {
2 public:
3     Solution() {
4         mp = {{'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}};
5     }
6
7     int strobogrammaticInRange(string low, string high) {
8         int ans = 0, l = low.length(), u = high.length();
9         for (int i = l; i <= u; i++) {
10             string temp(i, ' ');
11             strobogrammaticCount(temp, ans, low, high, 0, i - 1);
12         }
13         return ans;
14     }
15 private:
16     unordered_map<char, char> mp;
17     void strobogrammaticCount(string temp, int& ans, string& low, string& high, int lo, int hi) {
18         if (lo > hi) {
19             if ((temp[0] != '0' || temp.length() == 1) && less(low, temp) && less(temp, high))
20                 ans++;
21             return;
22         }
23         for (auto m : mp) {
24             temp[lo] = m.first;
25             temp[hi] = m.second;
26             if ((lo == hi && m.first == m.second) || lo < hi)
27                 strobogrammaticCount(temp, ans, low, high, lo + 1, hi - 1);
28         }
29     }
30     bool less(string& s, string& t) {
31         int m = s.length(), n = t.length(), i;
32         if (m != n) return m < n;
33         for (i = 0; i < m; i++)
34             if (s[i] == t[i]) continue;
35             else break;
36         return i == m || s[i] < t[i];
37     }
38 };

|
9月前
|

Leetcode 313. Super Ugly Number

80 1
|
2月前
|

LeetCode 题目 65：有效数字（Valid Number）【python】
LeetCode 题目 65：有效数字（Valid Number）【python】
36 5
|
3月前
|

【LeetCode力扣】单调栈解决Next Greater Number（下一个更大值）问题
【LeetCode力扣】单调栈解决Next Greater Number（下一个更大值）问题
23 0
|
9月前
|

Leetcode Single Number II （面试题推荐）

30 0
|

LeetCode 414. Third Maximum Number

78 0
|

LeetCode 405. Convert a Number to Hexadecimal

73 0
|
API
LeetCode 375. Guess Number Higher or Lower II

93 0
|
API
LeetCode 374. Guess Number Higher or Lower

64 0
|

LeetCode 321. Create Maximum Number

57 0
|

LeetCode 313. Super Ugly Number

82 0