753.破解保险箱

链接：753.破解保险箱
难度：Hard
标签：深度优先搜索、图、欧拉回路
简介：请返回一个能打开保险箱的最短字符串。

题解 1 - cpp

• 编辑时间：2023-01-10
• 执行用时：24ms
• 内存消耗：28.6MB
• 编程语言：cpp
• 解法介绍：dfs。

class Solution {
public:
    int n, k, nmax;
    string ans;
    unordered_set<string> visit;
    string crackSafe(int n, int k) {
        this->n = n;
        this->k = k;
        this->ans = "";
        for (int i = 0; i < n; i++) ans += "0";
        nmax = pow(k, n);
        visit.insert(ans);
        dfs(ans);
        return ans;
    }
    bool dfs(string cur) {
        string prefix = cur.substr(cur.size() - n + 1, n - 1);
        if (visit.size() == nmax) {
            ans = cur;
            return true;
        }
        for (int i = 0; i < k; i++) {
            string next = prefix + to_string(i);
            if (visit.count(next)) continue;
            visit.insert(next);
            if (dfs(cur + to_string(i))) return true;
            visit.erase(next);
        }
        return false;
    }
};

题解 2 - rust

• 编辑时间：2023-01-10
• 执行用时：12ms
• 内存消耗：19.6MB
• 编程语言：rust
• 解法介绍：同上。

use std::collections::HashSet;
impl Solution {
    pub fn crack_safe(n: i32, k: i32) -> String {
        let mut visit = HashSet::<String>::new();
        let mut cur = String::new();
        for _ in 0..n {
            cur.push('0');
        }
        visit.insert(cur.clone());
        Solution::dfs(n, k, &mut visit, cur).1
    }
    fn dfs<'a>(n: i32, k: i32, visit: &mut HashSet<String>, cur: String) -> (bool, String) {
        if visit.len() == k.pow(n as u32) as usize {
            (true, cur)
        } else {
            let pre = &cur[(cur.len() as i32 - n + 1) as usize..cur.len()];
            for i in 0..k {
                let mut next = String::from(pre);
                next.push(char::from(i as u8 + '0' as u8));
                if visit.contains(&next) {
                    continue;
                }
                visit.insert(next.clone());
                let mut cur = cur.clone();
                cur.push(char::from(i as u8 + '0' as u8));
                let res = Solution::dfs(n, k, visit, cur);
                if res.0 {
                    return res;
                }
                visit.remove(&next);
            }
            (false, "".to_string())
        }
    }
}