原题链接: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;
}
};