解决方案


方法:暴力法

思路

让我们试着逐位写一些答案中的数字。

对于除第一位数字之外的每位数字,该数字最多有两个选项。以 9 位数字为例,这意味着最多只能有 种可能。这小到足以使用暴力法来解决问题。

算法

一个 位数字可以看作只是在一个 位数字后添加了最后一位数字。如果该 位数字是以数字 结尾,则 位数字将以 结束(前提是这些数字在 之间)。我们将这些数字存储在 Set 结构中,以避免重复。

此外,我们应该注意前导零 —— 只有 1 位数字(数字 0)能以 0 开头。

复杂度分析

  • 时间复杂度:

  • 空间复杂度: