Problem#
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.
Examples#
Example 1:
1
2
3
4
5
|
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:
1
2
3
4
5
6
7
8
9
10
|
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.
|
Solution#
Method 1 – DFS and De Bruijn Sequence Construction#
Intuition#
The minimum string that unlocks the safe must contain every possible password of length n as a substring. This is equivalent to constructing a De Bruijn sequence of order n on k digits. We use DFS to build the sequence by visiting every possible combination exactly once.
Approach#
- Start with a string of
n-1 zeros as the initial node.
- Use DFS to explore all possible next digits, appending each digit to the sequence if the resulting substring hasn’t been visited.
- Mark each visited substring to avoid repeats.
- After visiting all possible combinations, append the initial node to complete the sequence.
- Return the constructed sequence.
Code#
Java#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public String crackSafe(int n, int k) {
StringBuilder ans = new StringBuilder();
Set<String> vis = new HashSet<>();
String start = "0".repeat(n - 1);
dfs(start, n, k, vis, ans);
ans.append(start);
return ans.toString();
}
void dfs(String node, int n, int k, Set<String> vis, StringBuilder ans) {
for (int i = 0; i < k; i++) {
String next = node + i;
if (!vis.contains(next)) {
vis.add(next);
dfs(next.substring(1), n, k, vis, ans);
ans.append(i);
}
}
}
}
|
C++#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public:
string crackSafe(int n, int k) {
string ans;
unordered_set<string> vis;
string start(n - 1, '0');
dfs(start, n, k, vis, ans);
ans += start;
return ans;
}
void dfs(string node, int n, int k, unordered_set<string>& vis, string& ans) {
for (int i = 0; i < k; ++i) {
string next = node + to_string(i);
if (!vis.count(next)) {
vis.insert(next);
dfs(next.substr(1), n, k, vis, ans);
ans += to_string(i);
}
}
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
func crackSafe(n int, k int) string {
vis := map[string]bool{}
var ans []byte
start := make([]byte, n-1)
for i := range start { start[i] = '0' }
var dfs func(string)
dfs = func(node string) {
for i := 0; i < k; i++ {
next := node + string('0'+i)
if !vis[next] {
vis[next] = true
dfs(next[1:])
ans = append(ans, byte('0'+i))
}
}
}
dfs(string(start))
return string(ans) + string(start)
}
|
Python#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution:
def crackSafe(self, n: int, k: int) -> str:
vis = set()
ans = []
start = '0' * (n - 1)
def dfs(node: str):
for i in range(k):
nxt = node + str(i)
if nxt not in vis:
vis.add(nxt)
dfs(nxt[1:])
ans.append(str(i))
dfs(start)
return ''.join(ans) + start
|
Rust#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
use std::collections::HashSet;
impl Solution {
pub fn crack_safe(n: i32, k: i32) -> String {
let mut vis = HashSet::new();
let mut ans = String::new();
let start = "0".repeat((n - 1) as usize);
fn dfs(node: &str, n: i32, k: i32, vis: &mut HashSet<String>, ans: &mut String) {
for i in 0..k {
let next = format!("{}{}", node, i);
if !vis.contains(&next) {
vis.insert(next.clone());
dfs(&next[1..], n, k, vis, ans);
ans.push_str(&i.to_string());
}
}
}
dfs(&start, n, k, &mut vis, &mut ans);
ans.push_str(&start);
ans
}
}
|
TypeScript#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
crackSafe(n: number, k: number): string {
const vis = new Set<string>();
let ans = '';
const start = '0'.repeat(n - 1);
function dfs(node: string) {
for (let i = 0; i < k; i++) {
const next = node + i;
if (!vis.has(next)) {
vis.add(next);
dfs(next.slice(1));
ans += i;
}
}
}
dfs(start);
return ans + start;
}
}
|
Complexity#
- ⏰ Time complexity:
O(k^n), since there are k^n possible passwords and each is visited once.
- 🧺 Space complexity:
O(k^n), for the visited set and recursion stack.