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`` 的字符。 自建示例 -------- 覆盖全部九种二位三进制密码: .. code-block:: text 输入:n = 2, k = 3 输出:"0010211220" 解释:长度为 2 的连续子串依次为 "00"、"01"、"10"、"02"、"21"、"11"、"12"、"22"、"20",正好覆盖由 0、1、2 组成的全部九种二位密码。九个不同子串至少需要 9 + 2 - 1 = 10 个字符,因此该输出长度最短;其他最短合法字符串也可以接受。 字符种类只有一种: .. code-block:: text 输入:n = 4, k = 1 输出:"0000" 解释:当 k = 1 时每一位只能是 0,因此唯一可能的四位密码是 "0000"。输出本身包含这个连续四位子串;少于四个字符时无法出现任何四位密码,所以该输出长度最短。