1088. Confusing Number II

We can rotate digits by 180 degrees to form new digits. When 0, 1, 6, 8, 9 are rotated 180 degrees, they become 0, 1, 9, 8, 6 respectively. When 2, 3, 4, 5 and 7 are rotated 180 degrees, they become invalid.

A confusing number is a number that when rotated 180 degrees becomes a different number with each digit valid.(Note that the rotated number can be greater than the original number.)

Given a positive integer N, return the number of confusing numbers between 1 and N inclusive.

Example 1:

Input: 20
Output: 6
Explanation: 
The confusing numbers are [6,9,10,16,18,19].
6 converts to 9.
9 converts to 6.
10 converts to 01 which is just 1.
16 converts to 91.
18 converts to 81.
19 converts to 61.

Example 2:

Input: 100
Output: 19
Explanation: 
The confusing numbers are [6,9,10,16,18,19,60,61,66,68,80,81,86,89,90,91,98,99,100].

Note:

1. 1 <= N <= 10^9

// Naive Recursion
void helper(long num, long rotate_num, const int& N, unordered_map<int, int>& rotate_mp, long base, int& res) {
    if (num != rotate_num) ++res;
    for (const auto& e : rotate_mp) {
        if (!e.first && !num) continue;
        long new_num = num * 10 + e.first;
        if (new_num > N) continue;
        helper(new_num, rotate_mp[e.first] * base + rotate_num, N, rotate_mp, base * 10, res);
    }
} 
int confusingNumberII(int N) {
    unordered_map<int, int> rotate_mp;
    rotate_mp[0] = 0;
    rotate_mp[1] = 1;
    rotate_mp[6] = 9;
    rotate_mp[8] = 8;
    rotate_mp[9] = 6;
    int res = 0;
    helper(0, 0, N, rotate_mp, 1, res);
    return res;
}

// Count numbers with digits in "01689" from 0 to s
int findAll(const string& s) {
    const string digits = "01689";
    if (s.length() == 1) {
        int res = 0;
        for (char c : digits) {
            if (c <= s[0]) ++res;
        }
        return res;
    } else {
        int smaller = 0;
        for (char c : digits) {
            if (c < s[0]) ++smaller;
        }
        int res = smaller * powl(5, s.length() - 1);
        if (digits.find(s[0]) != string::npos) res += findAll(s.substr(1));
        return res;
    }
}
int confusingNumberII(int N) { // time: O(5^len(num)); space: O(len(num))
    const string num = to_string(N);
    const vector<string> rotate_mp({"00", "11", "88", "69", "96"});
    const int num_len = num.length();
    vector<vector<string> > level(num_len + 1);
    level[0] = {""};
    int strobogrammatic_number = 0;
    for (int len = 1; len <= num_len; ++len) {
        if (len == 1) {
            level[len] = {"0", "1", "8"};
        } else {
            for (const string& middle : level[len - 2]) {
                for (const string& pair : rotate_mp) {
                    level[len].push_back(pair[0] + middle + pair[1]);
                }
            }
        }
        for (const string& t : level[len]) {
            if (len > 1 && t[0] == '0') continue;
            long n = stol(t);
            if (n <= N) ++strobogrammatic_number;
        }
    }
    // (# of confusing numbers = # of numbers with digits "01689" <= num) - (# of strobogrammatic numbers)
    return findAll(num) - strobogrammatic_number; 
}