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](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2024/02/LeetCode-Problem-Solution.png?resize=200%2C200&ssl=1)
Cracking the Safe LeetCode Solution
Table of Contents
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 recent3
digits is"0"
, which is incorrect. - After typing
1
, the most recent3
digits is"01"
, which is incorrect. - After typing
2
, the most recent3
digits is"012"
, which is incorrect. - After typing
3
, the most recent3
digits is"123"
, which is incorrect. - After typing
4
, the most recent3
digits is"234"
, which is incorrect. - After typing
5
, the most recent3
digits is"345"
, which is correct and the safe unlocks.
- After typing
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 4th digit. – “01” is typed in starting from the 1st digit. – “10” is typed in starting from the 3rd digit. – “11” is typed in starting from the 2nd digit. Thus “01100” will unlock the safe. “10011”, and “11001” would also unlock the safe.
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;
}
};
Code language: PHP (php)
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;
}
}
Code language: JavaScript (javascript)
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)
}
}
Code language: JavaScript (javascript)
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))