Algorithm
Problem Name: 753. Cracking the Safe
Problem Link: https://leetcode.com/problems/cracking-the-safe/
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 recent3digits is"0", which is incorrect. - After typing
1, the most recent3digits is"01", which is incorrect. - After typing
2, the most recent3digits is"012", which is incorrect. - After typing
3, the most recent3digits is"123", which is incorrect. - After typing
4, the most recent3digits is"234", which is incorrect. - After typing
5, the most recent3digits 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. "01100", "10011", and "11001" would also unlock the safe.
Constraints:
1 <= n <= 41 <= k <= 101 <= kn <= 4096
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
string crackSafe(int n, int k) {
int target = pow(k, n);
string res;
for (int i = 0; i < n; ++i) {
res += '0';
}
string cur = res;
unordered_set < string>visited;
dfs(res, target, visited, n, k, cur);
return res;
}
bool dfs(string& res, int& target, unordered_set < string>& visited, int n, int k, string cur) {
if (visited.count(cur)) {
return false;
}
visited.insert(cur);
if (visited.size() == target) {
return true;
}
string next = cur.substr(1);
for (int i = 0; i < k; ++i) {
next.push_back('0' + i);
if (!visited.count(next)) {
res.push_back('0' + i);
if (dfs(res, target, visited, n, k, next)) {
return true;
}
res.pop_back();
}
next.pop_back();
}
visited.erase(cur);
return false;
}
};
Input
n = 1, k = 2
Output
"10"
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def crackSafe(self, n, k):
s = '0' * (n - 1)
D = '9876543210'[-k:]
for _ in range(k**n):
s += next(d for d in D if (s + d)[-n:] not in s)
return s
Input
n = 1, k = 2
Output
"10"
#3 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Collections.Generic;
using System.Text;
namespace LeetCode
{
public class _0753_CrackingtheSafe
{
public string CrackSafe(int n, int k)
{
var totalSize = (int)Math.Pow(k, n);
var alreadySeen = new HashSet < string>();
var results = new StringBuilder();
var start = new string('0', n - 1);
DFS(start, k, totalSize, alreadySeen, results);
results.Append(start);
return results.ToString();
}
private void DFS(string currentString, int k, int totalSize, ISet < string> alreadySeen, StringBuilder results)
{
if (alreadySeen.Count == totalSize)
return;
for (int i = 0; i < k; i++)
{
var newString = currentString + i.ToString();
if (alreadySeen.Contains(newString))
continue;
alreadySeen.Add(newString);
DFS(newString.Substring(1), k, totalSize, alreadySeen, results);
results.Append(i);
}
}
}
}
Input
n = 2, k = 2
Output
"01100"