Last updated on October 9th, 2024 at 06:22 pm

Here, We see Cracking the Safe LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Cracking the Safe LeetCode Solution

Problem Statement

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 way of checking the password. When you enter in a sequence, it checks the most recent n digits that were entered each time you type a digit.

• For example, the correct password is "345" and you enter in "012345":
  • After typing 0, the most recent 3 digits is "0", which is incorrect.
  • After typing 1, the most recent 3 digits is "01", which is incorrect.
  • After typing 2, the most recent 3 digits is "012", which is incorrect.
  • After typing 3, the most recent 3 digits is "123", which is incorrect.
  • After typing 4, the most recent 3 digits is "234", which is incorrect.
  • After typing 5, the most recent 3 digits is "345", which is correct and the safe unlocks.

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

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

Example 2:
Input: n = 2, k = 2 Output: “01100” Explanation: For each possible password: – “00” is typed in starting from the 4^th digit. – “01” is typed in starting from the 1^st digit. – “10” is typed in starting from the 3^rd digit. – “11” is typed in starting from the 2^nd digit. Thus “01100” will unlock the safe. “10011”, and “11001” would also unlock the safe.

1. Cracking the Safe LeetCode Solution C++

class Solution {
public:
	string crackSafe(int n, int k) {
		unordered_map<string,int> m;
		string ans="";
		for(int i=0;i<n-1;i++)
		{
			ans+='0';
		}

		for(int i=0;i<pow(k,n);i++)
		{
			string temp=ans.substr(ans.size()-n+1,n-1);
			m[temp]=(m[temp]+1)%k;
			ans+=('0'+m[temp]);
		}

		return ans;
	}
};

2. Cracking the Safe LeetCode Solution Java

class Solution {
    public String crackSafe(int n, int k) {
        Set<String> visited = new HashSet<String>();
        String res = "";
        for(int j = 0; j < n; j++){
            res+=0;
        }
        int total = 1;
        for(int i = 0; i < n; i++){
            total *= k;
        }
        total += n-1;
        res=DFS(res, n, k, visited, total);
        return res;
    }
    private String DFS(String res, int n, int k, Set<String> visited, int total){
        int len = res.length();
        visited.add(res.substring(len-n, len));
        for(int i = 0; i < k; i++){
            if(!visited.contains(res.substring(len-n+1, len)+i)){
                String tmp = DFS(res+i, n, k, visited, total);
                if(tmp.length() == total){
                    res = tmp;
                    break;
                }
                visited.remove(res.substring(len-n+1, len)+i);
            }
        }     
        return res;
    }
}

3. Cracking the Safe LeetCode Solution JavaScript

var crackSafe = function (n, k) {
    if (n === 1 && k === 1) return '0'
    const visited = new Set()
    const seq = []
    const prefix = '0'.repeat(n - 1)
    dfs(prefix, seq, visited, k)
    seq.push(prefix)
    return seq.join('')
}

const dfs = (prefix, seq, visited, k) => {
  for (let i = 0; i < k; i++) {
    const combination = prefix + i.toString()
    if (visited.has(combination)) continue
    visited.add(combination)
    dfs(combination.slice(1), seq, visited, k)
    seq.push(i)
  }
}

4. Cracking the Safe LeetCode Solution Python

class Solution(object):
    def crackSafe(self, n, k):
        if n == 1:
            return ''.join(map(str, range(k)))
        seen = set()
        result = []
        start_node = "0" * (n - 1)
        self.dfs(start_node, k, seen, result)
        return "".join(result) + start_node

    def dfs(self, node, k, seen, result):
        for i in range(k):
            edge = node + str(i)
            if edge not in seen:
                seen.add(edge)
                self.dfs(edge[1:], k, seen, result)
                result.append(str(i))