查找子串避免使用递归函数

Question

我正在研究 Python 中的算法并解决一个问题：

让 x(k) 是一个递归定义的字符串，基本情况 x(1) = "123" 并且 x(k) 是 "1" + x(k-1) + "2" + x(k-1) + " 3”。给定三个正整数 k、s 和 t，找到子串 x(k)[s:t]。

例如，如果 k = 2，s = 1 且 t = 5，x(2) = 112321233 且 x(2)[1:5] = 1232。

我已经使用一个简单的递归函数解决了它：

   def generate_string(k):
        if k == 1:
            return "123"
            
        part = generate_string(k -1)
        return ("1" + part  + "2" + part + "3")
        print(generate_string(k)[s,t])

虽然我的第一种方法给出了正确的答案，但问题是当 k 大于 20 时构建字符串 x 花费的时间太长。当 k 小于 50 时，程序需要在 16 秒内完成。我尝试使用记忆化，但它没有帮助，因为我不允许缓存每个测试用例。因此我认为我必须避免使用递归函数来加速程序。有什么我应该考虑的方法吗？

Answer 1

我们可以看到由 表示的字符串的x(k) 长度随着k 的增加呈指数增长：

len(x(1)) == 3
len(x(k)) == len(x(k-1)) * 2 + 3

所以：

len(x(k)) == 3 * (2**k - 1)

对于k等于 100，这相当于长度超过 10 ³⁰。字符比人体内的原子还多！

由于参数s和t将（相比之下）占据其中的一小部分，因此您不需要生成整个字符串。您仍然可以使用递归，但要继续将s和t范围传递给每个调用。然后，当您看到此切片实际上将在您将生成的字符串之外时，您可以直接退出而无需更深入地递归，从而节省大量时间和（字符串）空间。

以下是您可以这样做的方法：

def getslice(k, s, t):
    def recur(xsize, s, t):
        if xsize == 0 or s >= xsize or t <= 0:
            return ""
        smaller = (xsize - 3) // 2
        return ( ("1" if s <= 0 else "")
               + recur(smaller, s-1, t-1)
               + ("2" if s <= smaller+1 < t else "")
               + recur(smaller, s-smaller-2, t-smaller-2)
               + ("3" if t >= xsize else "") )
    return recur(3 * (2**k - 1), s, t)

这不使用任何x(k)结果缓存......在我的测试中，这已经足够快了。