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 位序列 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<Alphabets: RandomAccessCollection>(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..<debruijnLength {
13         var current = index
14         while !used[current] {
15             used[current] = true
16             
17             let elementIndex = current / cycleCount
18             current = (current % cycleCount) * alphabetCount + elementIndex
19             result.append(alphabets[alphabets.index(alphabets.startIndex, offsetBy: elementIndex)])
20         }
21         assert(current == index)
22     }
23     
24     assert(result.count == debruijnLength)
25     return result
26 }
27 
28 class Solution {
29     func crackSafe(_ n: Int, _ k: Int) -> String {
30         let result = deBruijnSequence(of: (0..<k).map(String.init), length: n)
31         return (result + repeatElement("0", count: n - 1)).joined()
32     }
33 }

---

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<String>()
 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<String>, _ current: inout [Int]) -> Bool {
12         guard used.count < total else {
13             return true
14         }
15         var prefix = Array(current[(current.count - n + 1)...]).reduce("") { $0 + String($1) }
16         for num in 0..<k {
17             let currentSegment = prefix + String(num)
18             guard !used.contains(currentSegment) else {
19                 continue
20             }
21             used.insert(currentSegment)
22             current.append(num)
23             if dfs(n, k, total, &used, &current) {
24                 return true
25             }
26             current.removeLast()
27             used.remove(currentSegment)
28         }
29         return false
30     }
31 }

---

152ms

 1 class Solution {
 2     func dfs(_ n: Int, _ k: Int, _ len: Int, _ data: inout Set<String>, _ res:inout String) -> Bool {
 3         if (res.count == len) { return true; }
 4         let suf = res.suffix(n-1)
 5         for c in 0..<k {
 6             if !data.contains(suf + "\(c)") {
 7                 data.insert(suf + "\(c)")
 8                 res += "\(c)"
 9                 if (dfs(n, k, len, &data, &res)) {
10                     return true
11                 }
12                 data.remove(suf + "\(c)")
13                 res.removeLast()
14             }
15         }
16         return false
17     }
18     func crackSafe(_ n: Int, _ k: Int) -> String {
19         let len = Int(pow(Double(k), Double(n))) + n - 1
20         var res = String((0..<n).map{_ in Character("0")})
21         var data = Set([res])
22         dfs(n, k, len, &data, &res)
23         return res
24     }
25 }

---

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<String> = [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<String>,_ res:inout String)
11     {
12         if visited.count == total
13         {
14             return
15         }
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 ) -> String
31     {
32         var result = String()
33         for i in 0...times {
34             result += self
35         }
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..<end]) 
46     }    
47 }