Leetcode 1088: Confusing Number II

https://leetcode.com › problems › 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 <= N <= 10^9


Notes:

The N to this question can be very large, so checking one by one is not a good choice.

As indicated by the question itself, only 0, 1, 6, 8, and 9 are valid numbers. So we just need to check the numbers composed by them.

Since we will compare digits at different positions, so string can be a good choice for easier coding than integer.

Now the question becomes a typical backtracking one: we will try all the possible combinations, then check the qualification. If valid, count +1.

See the code below:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
 
using namespace std;
 
int findAllConfNums(int n);
 
void dfs(string t, string &s, string &nums, int &res);
 
int main() {
    int n = 100;
    int num = findAllConfNums(n);
    cout<<num;
    return 0;
}
 
int findAllConfNums(int n) {
    int res = 0;
    string s = to_string(n);
    string nums = "01689";
    dfs("", s, nums, res);
    return res;
}
 
void dfs(string t, string &s, string &nums, int &res) {
    if(t.size() > s.size() || t.size() == s.size() && t.compare(s) > 0) return;
    if(t.size() && t[0] == '0') return;
    string temp = t;
    reverse(temp.begin(), temp.end());
    for(int i=0; i<temp.size(); ++i) {
        if(temp[i] == '6') temp[i] = '9';
        else if(temp[i] == '9') temp[i] = '6';
    }
    if(t != temp) ++res;
    for(int i=0; i<nums.size(); ++i) {
        dfs(t + nums.substr(i, 1), s, nums, res);
    }
}