How can Depth-First Search help in solving Cracking the Safe?

DFS is critical for exploring all possible paths in Cracking the Safe, ensuring that all combinations are visited exactly once and optimizing the password sequence.

What is an Eulerian circuit, and why is it important for this problem?

An Eulerian circuit is a path that visits every edge in a graph exactly once, which is the key to solving Cracking the Safe, as it ensures every password combination is covered.

What are the constraints for the Cracking the Safe problem?

The constraints are 1 <= n <= 4, 1 <= k <= 10, and 1 <= kn <= 4096, which limit the possible password lengths and digit ranges.

What should I consider when choosing a graph traversal approach for this problem?

Choosing DFS and optimizing with backtracking or Eulerian circuits is important to efficiently traverse the password space without unnecessary re-exploration.

How does GhostInterview assist with solving Cracking the Safe?

GhostInterview provides interactive, graph-focused problem-solving steps that help candidates understand Eulerian circuits, DFS, and optimal traversal methods.

#753

Hard

auto_awesome图·DFS·traversal

LeetCode 题解工作台

破解保险箱

有一个需要密码才能打开的保险箱。密码是 n 位数, 密码的每一位都是范围 [0, k - 1] 中的一个数字。保险箱有一种特殊的密码校验方法，你可以随意输入密码序列，保险箱会自动记住最后 n 位输入，如果匹配，则能够打开保险箱。例如，正确的密码是 "345" ，并且你输入的是 "012345…

深度优先搜索图欧拉回路

题目描述

有一个需要密码才能打开的保险箱。密码是 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：

输入：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 <= n <= 4
1 <= k <= 10
1 <= kⁿ <= 4096

lightbulb

解题思路

方法一：欧拉回路

我们可以对题目中所描述的内容构建有向图：将每个点看作一个长度为 $n-1$ 的 $k$ 字符串，每条边都带有一个从 $0$ 到 $k-1$ 的字符。如果点 $u$ 到点 $v$ 之间有一条有向边 $e$ ，假设 $e$ 携带的字符为 $c$ ，那么 $u+c$ 的末尾 $k-1$ 个字符形成的字符串等于 $v$ ，此时边 $u+c$ 就表示了一个长度为 $n$ 的密码。

在这个有向图中，一共有 $k^{n-1}$ 个点，每个点都有 $k$ 条出边，也有 $k$ 条入边，因此，该有向图存在欧拉回路，欧拉回路所经过的路径拼接起来就是题目中的答案。

时间复杂度 $O(k^n)$ ，空间复杂度 $O(k^n)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def crackSafe(self, n: int, k: int) -> str:
        def dfs(u):
            for x in range(k):
                e = u * 10 + x
                if e not in vis:
                    vis.add(e)
                    v = e % mod
                    dfs(v)
                    ans.append(str(x))

        mod = 10 ** (n - 1)
        vis = set()
        ans = []
        dfs(0)
        ans.append("0" * (n - 1))
        return "".join(ans)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate's understanding of Eulerian circuits and graph traversal will be essential for solving this problem.
question_mark
Look for familiarity with depth-first search and backtracking techniques as key concepts for solving this efficiently.
question_mark
The ability to break down the problem into smaller graph-related subproblems and use traversal optimizations will be a critical signal of readiness.

warning

常见陷阱

外企场景

error
Failing to recognize the problem as a graph traversal one, leading to inefficient brute force solutions.
error
Not considering the constraints properly, which may result in unnecessary revisits to password combinations.
error
Overlooking the Eulerian circuit approach, which could lead to overly complex or incorrect solutions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing a different number of digits, which could alter the traversal space.
arrow_right_alt
Modifying the range of possible digits (k), potentially requiring a new approach to handle larger spaces.
arrow_right_alt
Changing the sequence length (n), making the problem easier or harder depending on the value of n.

help

常见问题

外企场景

继续练习

#332 重新安排行程 #743 网络延迟时间 #765 情侣牵手