Cracking the Safe
原题链接：https://leetcode.cn/problems/cracking-the-safe/description/
题目要求的是，某个时刻能够打开保险箱的任一最短密码序列，需要包含所有密码子串。
答案应当是一个字符串，任意长度为n的子串的都是一种密码方案。
对于有n位，每位k种方案的密码串，共有k^n个。
题目要求最短，那么任意位置选出的子串应当是不重复的。
也就是说，一个长度为n的滑动窗口，在移动k^n次后，应得到k^n个不同的密码串。
一次滑动得到的两个不同密码串，前者的n-1位后缀是后者的n-1位前缀。
题目要求长度为n，将长度为n-1的k^(n-1)个串作为图的节点。
通过追加[0,k)，可以得到k^n个密码串，每个串的后n-1位子串一定等于图中的某个节点。在追加字符前前的子串，和，追加字符后的子串的后n-1位子串，之间，建立一条有向边。
- 那么图中的每个节点都有
k条出边，指向k个不同的图中节点。 - 这
k个图中节点一定是不同的，因为最后一个字符，也就是新追加的字符，是不相等的。
对于任意节点a1a2...aiaj，通过在xa1a2...ai末尾追加最后一个字符aj取后缀后得到，首位被舍弃。
首位有[0,k)共k种情况，任意节点都有k的可选的状态来源：
- 那么图中的每个节点都有
k条入边，来自k个不同的图中节点。
那么图中的每个点，都有k条出边和入边。
那么任意节点出发，都有一条欧拉回路。
最暴力的写法是，枚举每一位所有可能的情况，将k^n个密码串拼接。但必然不是最短方案。
因为一定有密码串满足一者的后缀等于另一者的前缀，可以借此压缩密码串长度。
dfs过程分析
状态表示node：
- 集合：已经生成的串，的末尾
n-1个字符的状态压缩表示为node。 - 属性：从
node出发的最短序列
状态转移：
- 当前状态表示为
node，是一个长度为n-1的数字，表示最后n-1位数字。 - 在状态的末尾添加一个
k进制数字x，形成一个新的n位序列。
去重和记忆化：
- 通过
set<int> seen，记录所有已经访问过的状态，确保每个状态只被访问一次。 - 通过
nei % highset，取出新状态的高n-1位部分，如此递归，直到所有状态都被遍历。
字符串拼接：
- 在递归过程中，每当成功生成了一个新的状态，就将对应的
x，即当前状态后添加的数字，转化为字符，并将其添加到最终答案字符串中。 - 最后追加
n-1个'0'，表示起点，因为Hierholzer算法求的路径是逆序的。
class Solution {
public:string crackSafe(int n, int k) {int highset = pow(10, n - 1);set<int> seen;string ans;auto dfs = [&](auto dfs, int node) -> void {for (int x = 0; x < k; x++) {int nei = node * 10 + x;if (!seen.count(nei)) {seen.insert(nei);dfs(dfs, nei % highset);ans += x + '0';}}};dfs(dfs, 0);ans += string(n - 1, '0');return ans;}
};