Leetcode 753. 破解保险箱

题目

有一个需要密码才能打开的保险箱。密码是 n 位数, 密码的每一位是 k 位序列 0, 1, …, k-1 中的一个 。

你可以随意输入密码，保险箱会自动记住最后 n 位输入，如果匹配，则能够打开保险箱。

举个例子，假设密码是 “345”，你可以输入 “012345” 来打开它，只是你输入了 6 个字符.

请返回一个能打开保险箱的最短字符串。

测试样例

示例1:

输入: n = 1, k = 2
输出: "01"
说明: "10"也可以打开保险箱。

示例2:

输入: n = 2, k = 2
输出: "00110"
说明: "01100", "10011", "11001" 也能打开保险箱。

提示：

1. n 的范围是 [1, 4]。
2. k 的范围是 [1, 10]。
3. k^n 最大可能为 4096。

题解

深搜回溯dfs
我们知道n位编码，数字大小在0~k-1共k各数，因此对于密码可能有n^k种状态，题目要求便是生成最短的字符串可以表示所有的状态。我们使用深搜回溯算法。
构造字符串的过程中，当构造的字符串大于n位时，我们需要保证最后n位表示的状态是第一次出现，我们就依次生成每个状态，知道所有状态都已表示。详细过程见代码

代码

	unordered_map<string,int> have;
string ans;
bool dfs(string& x,int k,int n,int cnt,int target){
if(cnt == target){
ans = x;
return true;
}
for(int i=0; i<k; i++){
x.push_back('0'+i);
if(x.length() < n){
if(dfs(x,k,n,cnt,target))
return true;
}else{
string newS = x.substr(x.length()-n);
//获取最后n位
if(have[newS] == 0){
//保证第一次出现
have[newS] = 1;
if(dfs(x,k,n,cnt+1,target)) return true;
have[newS] = 0;
}
}
x.pop_back();
}
return false;
}
string crackSafe(int n, int k) {
int cnt = 1;
for(int i=0; i<n; i++)
cnt *= k;
//计算n^k,也就是所有状态数
string x;
dfs(x,k,n,0,cnt);
return ans;
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cracking-the-safe
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

最后

以上就是天真帽子为你收集整理的Leetcode 753. 破解保险箱 C++Leetcode 753. 破解保险箱的全部内容，希望文章能够帮你解决Leetcode 753. 破解保险箱 C++Leetcode 753. 破解保险箱所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。