---

0753. 破解保险箱

• 标签：深度优先搜索、图、欧拉回路
• 难度：困难

题目链接

• 0753. 破解保险箱 - 力扣

题目大意

描述：

有一个需要密码才能打开的保险箱。密码是 $n$ 位数, 密码的每一位都是范围 $[0, k - 1]$ 中的一个数字。

保险箱有一种特殊的密码校验方法，你可以随意输入密码序列，保险箱会自动记住 最后 $n$ 位输入，如果匹配，则能够打开保险箱。

• 例如，正确的密码是 "345"，并且你输入的是 "012345"：
• 输入 0 之后，最后 3 位输入是 "0"，不正确。
• 输入 1 之后，最后 3 位输入是 "01"，不正确。
• 输入 2 之后，最后 3 位输入是 "012"，不正确。
• 输入 3 之后，最后 3 位输入是 "123"，不正确。
• 输入 4 之后，最后 3 位输入是 "234"，不正确。
• 输入 5 之后，最后 3 位输入是 "345"，正确，打开保险箱。

要求：

在只知道密码位数 $n$ 和范围边界 $k$ 的前提下，请你找出并返回确保在输入的「某个时刻」能够打开保险箱的任一 最短「密码序列」。

说明：

• $1 \le n \le 4$。
• $1 \le k \le 10$。
• $1 \le k^n \le 4096$。

示例：

• 示例 1：

输入：n = 1, k = 2
输出："10"
解释：密码只有 1 位，所以输入每一位就可以。"01" 也能够确保打开保险箱。

• 示例 2：

输入：n = 2, k = 2
输出："01100"
解释：对于每种可能的密码：
- "00" 从第 4 位开始输入。
- "01" 从第 1 位开始输入。
- "10" 从第 3 位开始输入。
- "11" 从第 2 位开始输入。
因此 "01100" 可以确保打开保险箱。"01100"、"10011" 和 "11001" 也可以确保打开保险箱。

解题思路

思路 1：欧拉回路（Hierholzer 算法）

这道题本质上是求欧拉回路问题。

问题转化：

• 将每个 $n-1$ 位的数字序列看作一个节点。
• 如果在某个 $n-1$ 位序列后面添加一个数字 $d$，可以得到一个 $n$ 位密码，那么就从该节点连一条边到新的 $n-1$ 位序列（去掉第一位，加上 $d$）。
• 例如：$n=2, k=2$ 时，节点有 0 和 1，边有 00、01、10、11。
• 我们需要找到一条路径，经过所有边恰好一次（欧拉回路）。

Hierholzer 算法：

1. 从任意节点开始 DFS，每次选择一条未访问的边。
2. 将访问过的边标记，避免重复访问。
3. 当无法继续前进时，将当前节点加入结果（逆序）。
4. 最后将结果反转，得到欧拉回路。

思路 1：代码

class Solution:
    def crackSafe(self, n: int, k: int) -> str:
        if n == 1:
            return ''.join(map(str, range(k)))
        
        visited = set()
        result = []
        start = '0' * (n - 1)
        
        def dfs(node):
            for digit in range(k):
                edge = node + str(digit)
                if edge not in visited:
                    visited.add(edge)
                    # 下一个节点是去掉第一位，加上当前数字
                    next_node = edge[1:]
                    dfs(next_node)
                    result.append(str(digit))
        
        dfs(start)
        
        # 结果需要加上起始节点
        return ''.join(result[::-1]) + start

思路 1：复杂度分析

• 时间复杂度：$O(k^n)$。总共有 $k^n$ 个不同的 $n$ 位密码，需要遍历所有边。
• 空间复杂度：$O(k^n)$。需要存储访问过的边和递归栈。