rustgym/leetcode/
_753_cracking_the_safe.rs

1struct Solution;
2
3use std::collections::HashSet;
4
5impl Solution {
6    fn crack_safe(n: i32, k: i32) -> String {
7        let n = n as usize;
8        let k = k as usize;
9        let mut seq = vec![0; n];
10        let mut visited: HashSet<Vec<u8>> = HashSet::new();
11        visited.insert(seq.clone());
12        let size = k.pow(n as u32);
13        Self::dfs(1, &mut visited, &mut seq, k, n, size);
14        seq.into_iter().map(|b| (b'0' + b) as char).collect()
15    }
16    fn dfs(
17        start: usize,
18        visited: &mut HashSet<Vec<u8>>,
19        seq: &mut Vec<u8>,
20        k: usize,
21        n: usize,
22        size: usize,
23    ) -> bool {
24        if visited.len() == size {
25            return true;
26        }
27        for i in 0..k {
28            let mut suffix = seq[start..].to_vec();
29            suffix.push(i as u8);
30            if visited.insert(suffix.clone()) {
31                seq.push(i as u8);
32                if Self::dfs(start + 1, visited, seq, k, n, size) {
33                    return true;
34                };
35                seq.pop();
36                visited.remove(&suffix);
37            }
38        }
39        false
40    }
41}
42
43#[test]
44fn test() {
45    let n = 1;
46    let k = 2;
47    let res = "01".to_string();
48    assert_eq!(Solution::crack_safe(n, k), res);
49    let n = 2;
50    let k = 2;
51    let res = "00110".to_string();
52    assert_eq!(Solution::crack_safe(n, k), res);
53}
rustgym/leetcode/_753_cracking_the_safe.rs

rustgym/leetcode/
_753_cracking_the_safe.rs
