[每日一题]753.破解保险箱
753. 破解保险箱 有一个需要密码才能打开的保险箱。密码是 n 位数, 密码的每一位是 k 位序列 0, 1, …, k-1 中的一个 。
你可以随意输入密码，保险箱会自动记住最后 n 位输入，如果匹配，则能够打开保险箱。举个例子，假设密码是 “345”，你可以输入 “012345” 来打开它，只是你输入了 6 个字符。请返回一个能打开保险箱的最短字符串。
举例：
-
输入: n = 1, k = 2 输出: "01" 说明: "10"也可以打开保险箱。 -
输入: n = 2, k = 2 输出: "00110" 说明: "01100", "10011", "11001" 也能打开保险箱。
n=1, k=2的时候，就是说密码是1位，可能是0，也可能是1，那么这个答案就应该包含0，也包含1，顺序不要紧，只要按照这答案输入，遇到对的情况自然会打开。n=2, k=2，那么密码就可能是01、10、00、11，密码就应该包含这四种情况，看一下答案，”00110” , “01100”, “10011”, “11001”，是不是这四种答案每个里边都包含这个子串？n=3, k=2，那么密码就应该包含000、001、010、011…
Solution
import java.util.Collections;
import java.util.TreeSet;
class Solution {
TreeSet<String> visited;
StringBuilder res;
public String crackSafe(int n, int k) {
if(n == 1 && k == 1) return "0";
visited = new TreeSet<>();
res = new StringBuilder();
// 从顶点 00..0 开始
String start = String.join("", Collections.nCopies(n-1, "0"));;
findEuler(start, k);
res.append(start); // 回路添加最后的end顶点，end 就是 start
return res.toString(); // return new String(res);
}
public void findEuler(String curv, int k){
for(int i = 0; i < k; i ++){
// 往顶点的 k 条出边检查，顶点加一条出边就是一种密码可能
String nextv = curv + i;
if(!visited.contains(nextv)){
visited.add(nextv);
findEuler(nextv.substring(1), k);
res.append(i);
}
}
}
}
Hard题真的难懂，图论和欧拉回路不知道是什么。。下次研究研究在写一个分析吧。