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:
- n will be in the range [1, 4].
- k will be in the range [1, 10].
- k^n will be at most 4096.
一刷
题解：密码的长度为n, 我们会在[0, ..., k-1]这k个digit中选取数字， 并且不停地往后面添加，直到最后的n个digit与密码match, 求最小的长度的input一定可以解开密码。
DFS可以做的原因是，确保每一次都可以形成一次状态转移，否则pruning. 因为是欧拉回路和哈密顿图，所以可以保证存在每个状态只经过一次的路径。
欧拉回路：一笔画，每个边只经过一次。因为入度(n) == 出度(n),可以证明为欧拉回路。
哈密顿图：指定的起点前往指定的终点，途中经过所有其他节点且只经过一次，对于顶点个数大于2的图，如果图中任意不相邻的两点度的和大于或等於顶点总数，那这个图一定是哈密尔顿图。
如何判断一个图是不是哈密顿图？w(G-S)>|S|
S表示点的非空子集，|S|表示子集包括的点的数目
class Solution {
public String crackSafe(int n, int k) {
StringBuilder sb = new StringBuilder();
int total = (int) (Math.pow(k, n));
for (int i = 0; i < n; i++) sb.append('0');
Set<String> visited = new HashSet<>();
visited.add(sb.toString());
dfs(sb, total, visited, n, k);
return sb.toString();
}
private boolean dfs(StringBuilder sb, int goal, Set<String> visited, int n, int k) {
if (visited.size() == goal) return true;
String prev = sb.substring(sb.length() - n + 1, sb.length());//the next n-1 digit
for(int i=0; i<k; i++){
String cur = prev + i;
if(visited.contains(cur)) continue;//确保每次添加，都形成了一次状态转移
visited.add(cur);
sb.append(i);
if(dfs(sb, goal, visited, n, k)) return true;//不停throw,找到第一个就返回
else{
visited.remove(cur);
sb.delete(sb.length()-1, sb.length());
}
}
return false;
}
}
