Readme

753.Cracking-the-Safe

这道题是一个被研究过的经典问题，称为De Bruijin序列。Wikipedia有专门介绍的页面。这个问题可以转化为一个特定的有向图，求问是否有一条最短的路径使得能遍历所有的节点。答案是可以的，而且这个路径非常优秀，每个节点可以只需要访问一次，我们称这样的有向图是存在哈密尔顿路径的。

注意，De Buijing序列并不是唯一的，有很多种生成方式。这里介绍一个比较简单的算法。就是将已经经历过的密码组合，取前n-1位作为key，最后一位作为val，放入哈希表中。当我们想在序列里添加一个新字符的时候，取当前序列的末尾n-1位作为哈希表的key，看看它对应的val是多少（注意val是之前已经尝试过的），那么这次我就在序列后添加val+1，这样就能生成一个新的n位的密码组合（记得同时更新哈希表的key-val）。依次重复下去，直到生成所有的k^n种密码组合为止。

上面算法其实有个assumption，那就是任意的n-1位组成的key，恰好会在这个过程中出现k次，不会更多也不会更少。事实上这个assumption是满足的，但证明过程就不深究了。

Leetcode Link