0753. Cracking the Safe¶
题目信息¶
- 题号:
0753
- 难度:
Hard
- 主题:
字符串、组合覆盖、最短序列构造
- 原题:
- 重点:
密码由
0至k - 1的数字组成且长度为n;返回任意一个长度最短的输入字符串,使每种可能密码都作为长度为n的连续子串出现
题目重述¶
一个保险箱的密码长度为 n,每一位都可以是 0 至 k - 1 中的任一数字。保险箱会在每次输入新数字后检查最近输入的 n 个数字;只要它们恰好等于真实密码,保险箱就会打开。
请返回任意一个长度最短的数字字符串,使得无论真实密码是哪一种可能的长度 n 密码,在依次输入该字符串的过程中都必然出现过与之相同的连续 n 位子串。存在多个最短答案时可以返回其中任意一个。
1 <= n <= 4,1 <= k <= 10,并且 k^n <= 4096。返回字符串只能使用表示数字 0 至 k - 1 的字符。
自建示例¶
覆盖全部九种二位三进制密码:
输入:n = 2, k = 3
输出:"0010211220"
解释:长度为 2 的连续子串依次为 "00"、"01"、"10"、"02"、"21"、"11"、"12"、"22"、"20",正好覆盖由 0、1、2 组成的全部九种二位密码。九个不同子串至少需要 9 + 2 - 1 = 10 个字符,因此该输出长度最短;其他最短合法字符串也可以接受。
字符种类只有一种:
输入:n = 4, k = 1
输出:"0000"
解释:当 k = 1 时每一位只能是 0,因此唯一可能的四位密码是 "0000"。输出本身包含这个连续四位子串;少于四个字符时无法出现任何四位密码,所以该输出长度最短。