Cracking the Safe

本文主要是介绍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;}
};

这篇关于Cracking the Safe的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---