<分区>
您好，我有以下问题:
We have a safe with 4 digits (each digit is between 0-9) password. The safe will be open if you give to it a string that contains a sub string with the correct 4 digit password. For example: safe with the code 2345 will be open if you give for example the string '123456'. the safe will be open in this case after the digit 5. you need to give the shortest string that necessarily will open the safe.
我尝试了很多方法，但找不到比包含以下内容的原始字符串更好的方法:0000000100020003...
最佳答案
您的答案是使用 De Bruin sequence 。在 Python 中(来自维基百科):
def de_bruijn(k, n):
"""
De Bruijn sequence for alphabet k
and subsequences of length n.
"""
try:
# let's see if k can be cast to an integer;
# if so, make our alphabet a list
_ = int(k)
alphabet = list(map(str, range(k)))
except (ValueError, TypeError):
alphabet = k
k = len(k)
a = [0] * k * n
sequence = []
def db(t, p):
if t > n:
if n % p == 0:
sequence.extend(a[1:p + 1])
else:
a[t] = a[t - p]
db(t + 1, p)
for j in range(a[t - p] + 1, k):
a[t] = j
db(t + 1, t)
db(1, 1)
return "".join(alphabet[i] for i in sequence)
在你的情况下是:
print(de_bruijn("0123456789", 4))
输出一个巨大的数字，我不会在这里复制粘贴。
关于string - 打破保险箱，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34632778/