753. Cracking the Safe

Problem Description

There is a safe protected by a password. The password is a sequence of n digits where each digit can be in the range [0, k - 1].

The safe has a peculiar characteristic: as soon as you enter a sequence of k digits that matches the password, the safe will open. For example, assuming the password is "345", I can open it when I type "012345", but I cannot enter either "01234" or "0123456".

Return any string of minimum length that will unlock the safe at some point.

Examples:

Input: n = 1, k = 2
Output: "10"
Explanation: The password is a single digit, so enter each digit, "01" would also unlock the safe.

Input: n = 2, k = 2
Output: "01100"
Explanation: "01100" will unlock the safe. "01100", "10011", and "11001" would also unlock the safe.

Constraints:

• 1 ≤ n ≤ 4
• 1 ≤ k ≤ 10
• k^n will be in the range [1, 4096]

Python Solution

class Solution:
    def crackSafe(self, n: int, k: int) -> str:
        def dfs(node: str) -> bool:
            if len(seen) == total:
                return True
                
            for i in range(k):
                next_node = node[1:] + str(i)
                if next_node not in seen:
                    seen.add(next_node)
                    result.append(str(i))
                    if dfs(next_node):
                        return True
                    result.pop()
                    seen.remove(next_node)
            return False
        
        # Initialize
        seen = set()
        result = []
        total = k ** n
        
        # Start with n zeros
        start = "0" * n
        seen.add(start)
        result = list(start)
        
        # DFS to find the sequence
        dfs(start)
        
        return "".join(result)

Implementation Notes:

• Uses DFS to find a de Bruijn sequence
• Each node represents a sequence of n-1 digits
• Time complexity: O(k^n)
• Space complexity: O(k^n) for storing seen states

Java Solution

class Solution {
    private Set seen;
    private StringBuilder result;
    private int total;
    
    public String crackSafe(int n, int k) {
        seen = new HashSet<>();
        result = new StringBuilder();
        total = (int) Math.pow(k, n);
        
        // Start with n zeros
        String start = "0".repeat(n);
        seen.add(start);
        result.append(start);
        
        // DFS to find the sequence
        dfs(start, k);
        
        return result.toString();
    }
    
    private boolean dfs(String node, int k) {
        if (seen.size() == total) {
            return true;
        }
        
        for (int i = 0; i < k; i++) {
            String next = node.substring(1) + i;
            if (!seen.contains(next)) {
                seen.add(next);
                result.append(i);
                if (dfs(next, k)) {
                    return true;
                }
                result.setLength(result.length() - 1);
                seen.remove(next);
            }
        }
        
        return false;
    }
}

C++ Solution

class Solution {
private:
    unordered_set seen;
    string result;
    int total;
    
    bool dfs(const string& node, int k) {
        if (seen.size() == total) {
            return true;
        }
        
        for (int i = 0; i < k; i++) {
            string next = node.substr(1) + to_string(i);
            if (seen.count(next) == 0) {
                seen.insert(next);
                result += to_string(i);
                if (dfs(next, k)) {
                    return true;
                }
                result.pop_back();
                seen.erase(next);
            }
        }
        
        return false;
    }
    
public:
    string crackSafe(int n, int k) {
        total = pow(k, n);
        
        // Start with n zeros
        string start(n, '0');
        seen.insert(start);
        result = start;
        
        // DFS to find the sequence
        dfs(start, k);
        
        return result;
    }
};

JavaScript Solution

function crackSafe(n, k) {
    const seen = new Set();
    let result = '';
    const total = Math.pow(k, n);
    
    function dfs(node) {
        if (seen.size === total) {
            return true;
        }
        
        for (let i = 0; i < k; i++) {
            const next = node.slice(1) + i;
            if (!seen.has(next)) {
                seen.add(next);
                result += i;
                if (dfs(next)) {
                    return true;
                }
                result = result.slice(0, -1);
                seen.delete(next);
            }
        }
        
        return false;
    }
    
    // Start with n zeros
    const start = '0'.repeat(n);
    seen.add(start);
    result = start;
    
    // DFS to find the sequence
    dfs(start);
    
    return result;
}

C# Solution

public class Solution {
    private HashSet seen;
    private StringBuilder result;
    private int total;
    
    public string CrackSafe(int n, int k) {
        seen = new HashSet();
        result = new StringBuilder();
        total = (int)Math.Pow(k, n);
        
        // Start with n zeros
        string start = new string('0', n);
        seen.Add(start);
        result.Append(start);
        
        // DFS to find the sequence
        Dfs(start, k);
        
        return result.ToString();
    }
    
    private bool Dfs(string node, int k) {
        if (seen.Count == total) {
            return true;
        }
        
        for (int i = 0; i < k; i++) {
            string next = node.Substring(1) + i;
            if (!seen.Contains(next)) {
                seen.Add(next);
                result.Append(i);
                if (Dfs(next, k)) {
                    return true;
                }
                result.Length--;
                seen.Remove(next);
            }
        }
        
        return false;
    }
}

Implementation Notes:

• Uses DFS to find a de Bruijn sequence
• Each node represents a sequence of n-1 digits
• Time complexity: O(k^n)
• Space complexity: O(k^n) for storing seen states