In this guide, you will get 753. Cracking the Safe LeetCode Solution with the best time and space complexity. The solution to Cracking the Safe problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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.
Constraints:
1 <= n <= 4
1 <= k <= 10
1 <= kn <= 4096
Complexity Analysis
Time Complexity: O(k^{k^n}) \to O(k^n)
Space Complexity: O(k^n)
753. Cracking the Safe LeetCode Solution in C++
class Solution {
public:
string crackSafe(int n, int k) {
string ans(n, '0');
dfs(pow(k, n), n, k, {ans}, ans);
return ans;
}
private:
bool dfs(int passwordSize, int n, int k, unordered_set<string>&& seen,
string& path) {
if (seen.size() == passwordSize)
return true;
string prefix = path.substr(path.length() - n + 1);
for (char c = '0'; c < '0' + k; ++c) {
prefix.push_back(c);
if (!seen.contains(prefix)) {
seen.insert(prefix);
path.push_back(c);
if (dfs(passwordSize, n, k, std::move(seen), path))
return true;
path.pop_back();
seen.erase(prefix);
}
prefix.pop_back();
}
return false;
}
}; /* code provided by PROGIEZ */
753. Cracking the Safe LeetCode Solution in Java
class Solution {
public String crackSafe(int n, int k) {
final String allZeros = "0".repeat(n);
StringBuilder sb = new StringBuilder(allZeros);
dfs((int) Math.pow(k, n), n, k, new HashSet<>(Arrays.asList(allZeros)), sb);
return sb.toString();
}
private boolean dfs(int passwordSize, int n, int k, Set<String> seen, StringBuilder path) {
if (seen.size() == passwordSize)
return true;
StringBuilder prefix = new StringBuilder(path.substring(path.length() - n + 1));
for (char c = '0'; c < '0' + k; ++c) {
prefix.append(c);
final String prefixStr = prefix.toString();
if (!seen.contains(prefixStr)) {
seen.add(prefixStr);
path.append(c);
if (dfs(passwordSize, n, k, seen, path))
return true;
path.deleteCharAt(path.length() - 1);
seen.remove(prefixStr);
}
prefix.deleteCharAt(prefix.length() - 1);
}
return false;
}
} // code provided by PROGIEZ
753. Cracking the Safe LeetCode Solution in Python
class Solution:
def crackSafe(self, n: int, k: int) -> str:
passwordSize = k**n
path = '0' * n
seen = set()
seen.add(path)
def dfs(path: str) -> str:
if len(seen) == passwordSize:
return path
for c in map(str, range(k)):
node = path[-n + 1:] + c if n > 1 else c
if node not in seen:
seen.add(node)
res = dfs(path + c)
if res:
return res
seen.remove(node)
return dfs(path) # code by PROGIEZ
