# 753. Cracking the Safe 破解保险箱

## # 题目描述：

There is a box protected by a password. The password is `n` digits, where each letter can be one of the first `k` digits `0, 1, ..., k-1`.

You can keep inputting the password, the password will automatically be matched against the last `n` digits entered.

For example, assuming the password is `"345"`, I can open it when I type `"012345"`, but I enter a total of 6 digits.

Please return any string of minimum length that is guaranteed to open the box after the entire string is inputted.

Example 1:

``````Input: n = 1, k = 2
Output: "01"
Note: "10" will be accepted too.
``````

Example 2:

``````Input: n = 2, k = 2
Output: "00110"
Note: "01100", "10011", "11001" will be accepted too.
``````

Note:

1. n will be in the range [1, 4].
2. k will be in the range [1, 10].
3. k^n will be at most 4096.

## # 解题方法

n位的密码锁，每个位置可以有k个数，所以总的可能性是k ^ n个。然后我们从前n位是0的状态开始，每次在后面添加一个新的字符，同时使用set保存这个出现过的新密码。当新密码的种类数等于 k ^ n时，搜索截止。

python由于是值传递，可以通过给函数传list的方式，直接修改list内会导致外边的List也变化，但是传string不行。string是不可变的对象，函数内部修改string不会影响到外边。因此，如果需要动态生成字符串，可以把string变成list当做函数的参数。

``````class Solution(object):
def crackSafe(self, n, k):
"""
:type n: int
:type k: int
:rtype: str
"""
res = ["0"] * n
size = k ** n
visited = set()
if self.dfs(res, visited, size, n, k):
return "".join(res)
return ""

def dfs(self, res, visited, size, n, k):
if len(visited) == size:
return True
node = "".join(res[len(res) - n + 1:])
for i in range(k):
node = node + str(i)
if node not in visited:
res.append(str(i))
if self.dfs(res, visited, size, n, k):
return True
res.pop()
visited.remove(node)
node = node[:-1]
``````