python - 查找子字符串，避免使用递归函数

Question

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

Let x(k) be a recursively defined string with base case x(1) = "123" and x(k) is "1" + x(k-1) + "2" + x(k-1) + "3". Given three positive integers k,s, and t, find the substring x(k)[s:t].

For example, if k = 2, s = 1 and t = 5,x(2) = 112321233 and 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)

对于等于100的k，其长度超过1030。这比人体中存在的原子还要多!
由于参数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)结果的任何缓存...在我的测试中，这足够快。