## 题目描述：

LeetCode 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`.

## 解题思路：

```初始令输入密码串ans = '0' * (n - 1)，visits记录输入串已经出现过的所有密码组合

## Python代码：

``````class Solution(object):
def crackSafe(self, n, k):
"""
:type n: int
:type k: int
:rtype: str
"""
ans = "0" * (n - 1)
visits = set()
for x in range(k ** n):
current = ans[-n+1:] if n > 1 else ''
for y in range(k - 1, -1, -1):
if current + str(y) not in visits:
ans += str(y)
break
return ans
``````

``````import collections
so = Solution()
for n in range(1, 5):
for k in range(1, 11):
if k ** n > 4096: continue
ans = so.crackSafe(n, k)
vset = set(ans[x : x + n] for x in range(len(ans) - n + 1))
print 'k =', k, ' n =', n
print len(ans), len(vset), sorted(collections.Counter(ans).items()), '\n'
``````

Pingbacks已关闭。

1. 隔壁老汪 发布于 2018年1月16日 12:20 #

楼主的代码和 简介，我的是C++写的，用的是dfs，比你的长很多。。。惭愧。
我隐约感觉这个题目应该是某种数学里循环置换群，我用英语搜了很多资料，找不到。。。

2. Zhiming Qin 发布于 2018年7月20日 04:01 #

如果用图论来考虑这个问题：把每种可能的key想成一个顶点，那么任意一个顶点与其他的n-1个顶点连接。这个问题就变成图论里的货郎担问题。不确定。