跳转至

LeetCode: 753. 破解保险箱

1、题目描述

有一个需要密码才能打开的保险箱。密码是 n 位数, 密码的每一位是 k 位序列 0, 1, ..., k-1 中的一个 。

你可以随意输入密码,保险箱会自动记住最后 n 位输入,如果匹配,则能够打开保险箱。

举个例子,假设密码是 "345",你可以输入 "012345" 来打开它,只是你输入了 6 个字符.

请返回一个能打开保险箱的最短字符串。

示例1:

输入: n = 1, k = 2
输出: "01"
说明: "10"也可以打开保险箱。

示例2:

输入: n = 2, k = 2
输出: "00110"
说明: "01100", "10011", "11001" 也能打开保险箱。

提示:

  • n 的范围是 [1, 4]。
  • k 的范围是 [1, 10]。
  • k^n 最大可能为 4096。

2、解题思路

  • 这道题经过分析可得,如果想要变得最短,每一种答案尽量利用前面答案的后缀,每次变更一个数字
  • (n-1)看成是一个节点,在这个节点前面和后面都补上一个数字,这个数字在[0,k-1]之间
  • 因此,可以看成是一条边,前面的看成入度,后面的看成出度,入度和出度都是k
  • 当前节点下一个状态是什么呢?就是当前节点加上边的字符,得到一个答案,答案去掉首字符,在这种情况下,所有的节点变成了一个图,每个节点的出度和入度都是k,因此是一个欧拉回路
  • 从一个起始状态开始,走完所有的边,加上起始状态就是最短的
class Solution:
    def crackSafe(self, n: int, k: int) -> str:
        visited = set()
        ans = []

        def dfs(node):
            for x in map(str, range(k)):
                status = node + x
                if status not in visited:
                    visited.add(status)
                    dfs(status[1:])
                    ans.append(x)

        start = "0" * (n - 1)
        dfs(start)
        return "".join(ans) + start