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算法求的路径是逆序的。

代码语言：javascript复制

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;
    }
};

遍历递归集合压缩字符串

0 人点赞

Cracking the Safe

dfs过程分析

`dfs`过程分析