特殊字符串序列的时间复杂度

Question

问题：有一个特殊的字符串序列，其中第 n 个字符串等于：前一个字符串 + "0" + 前一个字符串

S1 = 1，S2 = 101，S3 = 1010101，S4 = 101010101010101

请问求第n个字符串的第k个字符的最小时间复杂度是多少？我可以这样做而不找到字符串序列中的每个先前元素吗？

Answer 1

我认为使用 1 和 0 时很难看出规律，所以我们改用字母。

S1 = abc S2 = abc-d-abc S3 = abcdabc-d-abcdabc

模式现在更明显了。你总是有 S1 + d + S1 + d + ... + S1.

长度为S1.length * n + (n - 1)。模式长度是 4。所以长度并不重要，第 k 个字符是 (S1 + d)[k % 4] 其中 k < length.

如果不生成新字符串，时间复杂度为 O(1)。