[leetcode] Strobogrammatic Number III

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.

For example,
Given low = “50”, high = “100”, return 3. Because 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.

DFS generate all strobogrammatic numbers given the number of digits.

compare two strings.

```class Solution {
public:
unordered_map<char, char> mp = {{'0','0'}, {'1','1'}, {'6','9'}, {'8','8'}, {'9','6'}};
int strobogrammaticInRange(string low, string high) {
int count = 0;
for(int i = low.size(); i <= high.size(); i++){
vector<string> ans = gen(i);
if(i > low.size() && i < high.size()){
count += ans.size();
}
else{
for(auto it = ans.begin(); it != ans.end(); it++){
if(cmp(*it, low) && cmp(high, *it)){
count++;
}
}
}
}
return count;
}

vector<string> gen(int n){
vector<string> ans;
string thisAns(n, 0);
DFS(n, 0, ans, thisAns);
return ans;
}
void DFS(int n, int pos, vector<string>& ans, string& thisAns){
if(pos == n / 2 && n % 2 == 1){
//base condition, odd length
thisAns[pos] = '0';
ans.push_back(thisAns);
thisAns[pos] = '1';
ans.push_back(thisAns);
thisAns[pos] = '8';
ans.push_back(thisAns);
return ;
}
if(pos == n / 2&& n % 2 == 0){
//base condition, even length
ans.push_back(thisAns); // BUG HERE
return ;
}
//ordinary condition
int rpos = n - pos - 1;
for(auto it = mp.begin(); it != mp.end(); it++){
thisAns[pos] = it->first;
thisAns[rpos] = it->second;
if(thisAns[0] == '0') continue;//illegal number
DFS(n, pos + 1, ans, thisAns);
}
}
bool cmp(string a, string b){
// a >= b return true
// a < b return false
if(a.size() > b.size()) return true;
if(a.size() < b.size()) return false;

for(int i = 0; i < a.size(); i++){
if(a[i] > b[i]) return true;
else if(a[i] < b[i]) return false;
}
return true;// a == b
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.