Google – Password Sequence
有个保险箱，密码是四位0-9组成的数字，要求返回一个最短的暴力破解password sequence.
对于常见的保险箱，我们可以连续尝试保险箱的密码，比如当输入12345时，其实已经尝试了两个密码，1234和2345。而题目的意思就是找出一串最短的暴力破解序列，包含所有密码的可能性。
[Analysis]
从0000到9999一共有10000个数，也就是10000个密码。 由题意可以得到，最终最短的暴力破解序列长度应该为10003。
[Solution]
这道题其实是一道，Hamilton Cycle问题。每个vertex就是一个密码，如果当前密码的后三位数和另一个密码的前三位数一样，那么这两个节点之间就有一条edge. 每个vertex有10个adjacent nodes. 我们要做的就是在这个graph当中找出一条Hamilton Path.
但是实际的算法并没有那么复杂，并不需要另开数据结构来构建10000个节点的graph. 而是直接做backtracking.
而且仔细阅读这段code会发现其实也根本没有回溯，只是开了一个HashSet来保存遍历过的数字，不断尝试0000-9999之间的数字直到所有都遍历过为止。
有个保险箱，密码是四位0-9组成的数字，要求返回一个最短的暴力破解password sequence.
对于常见的保险箱，我们可以连续尝试保险箱的密码，比如当输入12345时，其实已经尝试了两个密码，1234和2345。而题目的意思就是找出一串最短的暴力破解序列，包含所有密码的可能性。
[Analysis]
从0000到9999一共有10000个数，也就是10000个密码。 由题意可以得到，最终最短的暴力破解序列长度应该为10003。
[Solution]
这道题其实是一道，Hamilton Cycle问题。每个vertex就是一个密码，如果当前密码的后三位数和另一个密码的前三位数一样，那么这两个节点之间就有一条edge. 每个vertex有10个adjacent nodes. 我们要做的就是在这个graph当中找出一条Hamilton Path.
但是实际的算法并没有那么复杂，并不需要另开数据结构来构建10000个节点的graph. 而是直接做backtracking.
而且仔细阅读这段code会发现其实也根本没有回溯，只是开了一个HashSet来保存遍历过的数字，不断尝试0000-9999之间的数字直到所有都遍历过为止。
public String passwordSequence() { int start = 9999; String result = "" + start; Set<Integer> visited = new HashSet<>(); visited.add(start); while (visited.size() < 10000) { int next = start * 10 % 10000; int i = 0; while (i <= 9) { if (visited.contains(next + i)) { i++; } else { break; } } visited.add(next + i); start = next + i; result += i; } }
同样地，对于 0 到 9 组成的全部四位数来说，我们可以设置 1000 个顶点，分别记作 000, 001, …, 999。如果某个数的后两位等于另一个数的前两位，就从前者出发，画一个箭头指向后者。容易想到，每个顶点的入度和出度都是 10，因此存在一条一笔画路径。也就是说，只需要按 10003 次数字键，便能试遍所有可能的四位数密码了。
Read full article from Google – Password Sequence
