python - 编程面试的要素-看和说

Question

查看Elements of Programming Interviews并查看以下问题：
在“看”和“说”（或“数”和“说”）序列中找出第n项look and say序列是以下整数的序列：
1，11，21，1211，111221，312211，13112221，1113213211…
作者的解决方案如下：

def look_and_say(n):
  def next_number(s):
    result, i = [], 0 
    while i < len(s):
      count = 1 
      while i + 1 < len(s) and s[i] == s[i + 1]:
        i += 1 
        count += 1
      result.append(str(count) + s[i])
      i += 1 
    return ''.join(result)

  s = '1'
  for _ in range(1, n):
     s = next_number(s)
  return s

我的问题是：递归调用（发生O(2^N)次）同时生成数组和字符串。我知道这只是空间开销中的一个常数因子，但是使用递归函数构建一个列表，然后不是return s，而是返回''.join(s)，不是更有效吗？

Answer 1

Python字符串是immutable，这意味着通过一次一个迭代来构造一个长字符串，每次迭代都会使字符串的实例加倍虽然早期的演进可能是垃圾收集，但从概念上讲，这仍然比附加到列表的效率低。
要生成字符串，1113213211将创建所有这些实例：

11
1113
111321
11132132
1113213211

正如作者所做的那样，生成列表将是：

['11', '13', '21', '32', '11']

（顺便说一下，在本例中，look_and_say函数调用其内部函数，next_number。这不是递归。要使其成为递归，其中一个函数必须调用自身。）