Python代码运行时间过长。

Question

我给出的问题是将所有"o“和"k”改为"ok“1000次，从"ok”开始，然后计算连续o有多少次。当代码达到两位数时，代码会显著减慢，我不知道该如何重构我的代码。

import string
y ="ok"
z = ""
for c in range(1000):
    for x in y:
        if str(x) == "o":
            x = x.replace("o", "ko")
            z += x
        else:
            x = x.replace("k", "ok")
            z += x
        y = z
    z = ""
    print(y,c)
y = y.replace("k", " ")
y = y.count("oo")
print (y)

源问题

基思对朋友长篇大论后，收到了一个由一个字母组成的信息："K“。这种低努力的反应激怒了他，他用"OK“来回应，他的朋友回答说”怪怪的“。作为一个精明的人，基思识别了他的朋友所倡导的模式:随后的信息包括基思和他的朋友将每个"K“替换为"OK”，"O“替换为"KO”。帮助基思在1000条回复的消息中找到长度为2或更长的连续Os集合。第一条消息"K“不算作回复。给你答案10^9 + 7。 为了澄清什么构成“长度为2或更长的连续Os集”：KOKOOKOOOKOOOO在这串中有三组长度为2或更长的连续K ("OO“、"OOO”、"OOOO")。

Answer 1

这里的主要问题是，每一步的字母数都会翻倍--比如说，在第40步，有2^40个字母。如果每个字母都有一个字节，那大约是兆字节的字母。当然，与存储所有1000步所需的空间相比，这只是一小部分。所以，不，野蛮地强迫这样的问题是不可行的。

相反，目标很可能会认识到模式是Thue-Morse序列，除非有时会掉转。“o”和“k”对应于0或1，这并不特别重要。您可以搜索维基百科页面，以找到序列中连续“1”的最大数量。

Answer 2

y ="ok"
for c in range(1000):
    y = y.replace('o','ko')
    y = y.replace('k','ok')
    print(y,c)

您可能不必在循环中搜索'o‘，'k’替换将为您做它，但它将需要很长的时间。