有一个需要密码才能打开的保险箱。 密码是 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" 也能打开保险箱。
提示:
n 的范围是 [1, 4]。
k 的范围是 [1, 10]。
k^n 最大可能为 4096。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/cracking-the-safe 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
int kind;
unordered_set<int> s;
string ans;
vector<int> unit = {0, 1, 10, 100, 1000};
public:
string crackSafe(int n, int k) {
kind = pow(k, n);//有多少种密码
string temp(n, '0');//第一种全零的
temp.reserve(10000);
s.insert(0);
dfs(temp, 0, n, k);
return ans;
}
void dfs(string& temp, int num, int n, int k)
{
if(ans != "")
return;
if(s.size() == kind)
{
ans = temp;//找到一种答案
return;
}
int newnum;
for(int i = 0; i < k; i++)
{
newnum = num - unit[n]*(temp[temp.size()-n]-'0');
temp += char('0'+i);
newnum = newnum*10 + i;
if(!s.count(newnum))
{
s.insert(newnum);
dfs(temp, newnum, n, k);
s.erase(newnum);
}
temp.pop_back();
}
}
};
56 ms 11.2 MB C++