1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
impl Solution {
pub fn confusing_number_ii(n: i32) -> i32 {
let digits = [0, 1, 6, 8, 9];
let mp = [(0,0),(1,1),(6,9),(8,8),(9,6)];
let mut map = std::collections::HashMap::new();
for (k,v) in mp.iter() { map.insert(*k, *v); }
fn is_confusing(mut x: i64, map: &std::collections::HashMap<i32,i32>) -> bool {
let orig = x;
let mut rot = 0;
while x > 0 {
rot = rot * 10 + map[&((x % 10) as i32)] as i64;
x /= 10;
}
rot != orig
}
fn dfs(x: i64, n: i64, digits: &[i32], map: &std::collections::HashMap<i32,i32>) -> i32 {
if x > n { return 0; }
let mut cnt = 0;
if x != 0 && is_confusing(x, map) { cnt += 1; }
for &d in digits {
if x == 0 && d == 0 { continue; }
let nx = x * 10 + d as i64;
if nx > n { break; }
cnt += dfs(nx, n, digits, map);
}
cnt
}
dfs(0, n as i64, &digits, &map)
}
}
|