题目描述：

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.

题目大意：

一个密码锁，其预设密码为n位，当输入一个字符串的后n位与预设密码相同时即可开启。

假设密码的每一位数字范围为0 ~ k-1，求长度最小的输入密码串，使得密码锁一定可以开启。

解题思路：

构造答案

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

从k - 1到0倒序枚举字符y，使得ans的后n位没有在visits中出现过

若找到这样的c，则将ans的后n位加入visits，并令ans += y

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:
                    visits.add(current + str(y))
                    ans += str(y)
                    break
        return ans

上述解法的正确性我也不会证明，o(╯□╰)o，但是枚举了所有的测试用例，结果均正确

测试Python代码：

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'

 

本文链接：http://bookshadow.com/weblog/2017/12/24/leetcode-cracking-the-safe/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码