# 753. Cracking the Safe

There is a box protected by a password. The password is `n` digits, where each letter can be one of the first `k` digits `0, 1, ..., k-1`.

You can keep inputting the password, the password will automatically be matched against the last `n` digits entered.

For example, assuming the password is `"345"`, I can open it when I type `"012345"`, but I enter a total of 6 digits.

Please return any string of minimum length that is guaranteed to open the box after the entire string is inputted.

Example 1:

``````Input: n = 1, k = 2
Output: "01"
Note: "10" will be accepted too.
``````

Example 2:

``````Input: n = 2, k = 2
Output: "00110"
Note: "01100", "10011", "11001" will be accepted too.
``````

Note:

1. `n` will be in the range `[1, 4]`.
2. `k` will be in the range `[1, 10]`.
3. `k^n` will be at most `4096`.

00，01，10，11

``````class Solution {
public:
string crackSafe(int n, int k) {
string res = string(n, '0');
unordered_set<string> visited{{res}};
for (int i = 0; i < pow(k, n); ++i) {
string pre = res.substr(res.size() - n + 1, n - 1);
for (int j = k - 1; j >= 0; --j) {
string cur = pre + to_string(j);
if (!visited.count(cur)) {
visited.insert(cur);
res += to_string(j);
break;
}
}
}
return res;
}
};
``````

``````class Solution {
public:
string crackSafe(int n, int k) {
string res = string(n, '0');
unordered_set<string> visited{{res}};
helper(n, k, pow(k, n), visited, res);
return res;
}
void helper(int n, int k, int total, unordered_set<string>& visited, string& res) {
if (visited.size() == total) return;
string pre = res.substr(res.size() - n + 1, n - 1);
for (int i = k - 1; i >= 0; --i) {
string cur = pre + to_string(i);
if (visited.count(cur)) continue;
visited.insert(cur);
res += to_string(i);
helper(n, k, total, visited, res);
}
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/753

https://leetcode.com/problems/cracking-the-safe/

https://leetcode.com/problems/cracking-the-safe/discuss/110264/Easy-DFS

https://leetcode.com/problems/cracking-the-safe/discuss/112966/C++-greedy-loop-from-backward-with-explaination

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation