0753. Cracking the Safe

题目信息

题号:

0753

难度:

Hard

主题:

字符串、组合覆盖、最短序列构造

原题:

LeetCode 0753

重点:

密码由 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"。输出本身包含这个连续四位子串;少于四个字符时无法出现任何四位密码,所以该输出长度最短。