[LeetCode]Cracking the Safe

题目描述:

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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

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

Pingbacks已关闭。

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

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

张贴您的评论