解决方案


方法:逆向工作法

思路

如果我们有一个像 appleappleappleappleappleapple 这样的解码字符串和一个像 K=24 这样的索引,那么如果 K=4,答案是相同的。

一般来说,当解码的字符串等于某个长度为 size 的单词重复某些次数(例如 applesize=5 组合重复6次)时,索引 K 的答案与索引 K % size 的答案相同。

我们可以通过逆向工作,跟踪解码字符串的大小来使用这种洞察力。每当解码的字符串等于某些单词 word 重复 d 次时,我们就可以将 k 减少到 K % (Word.Length)

算法

首先,找出解码字符串的长度。之后,我们将逆向工作,跟踪 size:解析符号 S[0], S[1], ..., S[i] 后解码字符串的长度。

如果我们看到一个数字 S [i],则表示在解析 S [0],S [1],...,S [i-1] 之后解码字符串的大小将是 size / Integer(S[i])。 否则,将是 size - 1

复杂度分析

  • 时间复杂度:,其中 S 的长度。

  • 空间复杂度: