1088. Confusing Number II

A confusing number is a number that when rotated 180 degrees becomes a different number with each digit valid.

We can rotate digits of a number by 180 degrees to form new digits.

• When 0, 1, 6, 8, and 9 are rotated 180 degrees, they become 0, 1, 9, 8, and 6 respectively.
• When 2, 3, 4, 5, and 7 are rotated 180 degrees, they become invalid.

Note that after rotating a number, we can ignore leading zeros.

• For example, after rotating 8000, we have 0008 which is considered as just 8.

Given an integer n, return the number of confusing numbers in the inclusive range [1, n].

class Solution {
    int res = 0;
    vector<char> numbers{'0','1','6','9','8'};
    bool bigger(string& origin, string& target) {
        if(origin.length() != target.length()) return origin.length() > target.length();
        for(int i = 0; i < origin.length(); i++) {
            if(origin[i] > target[i]) return true;
            else if(origin[i] < target[i]) return false;
        }
        return true; //origin == target;
    }
    bool valid(string& s) {
        if(s.length() <= 1) return false;
        int l = 0, r = s.length() - 1;
        while(l < r) {
            switch (s[l]) {
                case '0':
                case '1':
                case '8': if(s[r] != s[l]) return true;
                    break;
                case'6': if(s[r] != '9') return true; break;
                case'9': if(s[r] != '6') return true; break;
            }
            l++, r--;
        }
        return l == r and (s[l] == '6' or s[l] == '9');
    }
    void backTracking(string& t, string& o) {
        if(!bigger(o,t)) return;
        res += valid(t);
        for(auto& n : numbers) {
            t += n;
            backTracking(t, o);
            t.pop_back();
        }
    }
public:
    int confusingNumberII(int n) {
        string N = to_string(n);
        string one = "1", six = "6", eight = "8", nine = "9";
        backTracking(one,N);
        backTracking(six,N);
        backTracking(eight,N);
        backTracking(nine,N);
        return res + (n >= 6) + (n >= 9);
    }
};