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

Avoid heading 0s.

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
    }
};

 

Leave a comment

Your email address will not be published.

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