★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

➤微信公众号：山青咏芝（shanqingyongzhi）

➤博客园地址：山青咏芝（）

➤GitHub地址：

➤原文地址：  

➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。

➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

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 = 2Output: "01"Note: "10" will be accepted too. 

Example 2:

Input: n = 2, k = 2Output: "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 位序列 0, 1, ..., k-1 中的一个 。

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

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

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

示例1:

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

示例2:

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

提示：

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

---

12ms

1 func deBruijnSequence
     
      (of alphabets:Alphabets, length: Int) -> [Alphabets.Element] { 2     typealias Alphabet = Alphabets.Element 3      4     let alphabetCount = alphabets.count 5     let cycleCount = repeatElement(alphabetCount, count: length - 1).reduce(1, *) 6     let debruijnLength = cycleCount * alphabetCount 7      8     var used = Array(repeating: false, count: debruijnLength) 9     var result: [Alphabet] = []10     result.reserveCapacity(debruijnLength)11     12     for index in 0..
      
        String {30         let result = deBruijnSequence(of: (0..
      
     

---

36ms

1 class Solution { 2     func crackSafe(_ n: Int, _ k: Int) -> String { 3         let total = Int(pow(Double(k), Double(n))) 4         var current = [Int](repeating: 0, count: n) 5         var used = Set
     
      () 6         used.insert(current.reduce("") { $0 + String($1) }) 7         dfs(n, k, total, &used, &current) 8         return current.reduce("") { $0 + String($1) } 9     }10         11     private func dfs(_ n: Int, _ k: Int, _ total: Int, _ used: inout Set
      
       , _ current: inout [Int]) -> Bool {12         guard used.count < total else {13             return true14         }15         var prefix = Array(current[(current.count - n + 1)...]).reduce("") { $0 + String($1) }16         for num in 0..
      
     

---

152ms

1 class Solution { 2     func dfs(_ n: Int, _ k: Int, _ len: Int, _ data: inout Set
     
      , _ res:inout String) -> Bool { 3         if (res.count == len) { return true; } 4         let suf = res.suffix(n-1) 5         for c in 0..
      
        String {19         let len = Int(pow(Double(k), Double(n))) + n - 120         var res = String((0..
      
     

---

Runtime: 320 ms

Memory Usage: 22.2 MB

1 class Solution { 2     func crackSafe(_ n: Int, _ k: Int) -> String { 3         var res:String = "0".repeatString(n - 1) 4         var visited:Set
      
        = [res] 5         var num:Int = Int(pow(Double(k), Double(n))) 6         helper(n, k,num, &visited, &res) 7         return res 8     } 9     10     func helper(_ n:Int,_ k:Int,_ total:Int,_ visited:inout Set
       
        ,_ res:inout String)11     {12         if visited.count == total13         {14             return15         }16         var pre:String = res.subString(res.count - n + 1, n - 1)17         for i in stride(from:k - 1,through:0,by:-1)18         {19             var cur:String = pre + String(i)20             if visited.contains(cur) {
    continue}21             visited.insert(cur)22             res += String(i)23             helper(n, k, total, &visited, &res)24         }        25     }26 }27 28 extension String {29     //获取重复指定次数的字符串30     func repeatString(_ times: Int ) -> String31     {32         var result = String()33         for i in 0...times {34             result += self35         }36         return result 37     }38     39     // 截取字符串：指定索引和字符数40     // - begin: 开始截取处索引41     // - count: 截取的字符数量42     func subString(_ begin:Int,_ count:Int) -> String {43         let start = self.index(self.startIndex, offsetBy: max(0, begin))44         let end = self.index(self.startIndex, offsetBy:  min(self.count, begin + count))45         return String(self[start..