相关疑难解决方法(0)

我正在研究Allen Downey的" 如何像计算机科学家一样思考",并且我已经编写了我认为是练习10.10的功能正确的解决方案.但是运行起来只需要10个多小时(!),所以我想知道我是否缺少一些非常明显且有用的优化.

这是练习:

"两个单词'互锁',如果从每个单词中取代交替的字母形成一个新单词.例如,'shoe'和'cold'互锁形成'schooled'.编写一个程序,找到所有互锁的单词对.提示:Don'列举所有对!"

(对于这些单词列表问题,Downey提供了一个包含113809个单词的文件.我们可以假设这些单词在列表中,列表中每个项目一个单词.)

这是我的解决方案:

from bisect import bisect_left

def index(lst, target):
    """If target is in list, returns the index of target; otherwise returns None"""
    i = bisect_left(lst, target)
    if i != len(lst) and lst[i] == target:
        return i
    else:
        return None

def interlock(str1, str2):
    "Takes two strings of equal length and 'interlocks' them."
    if len(str1) == len(str2):
        lst1 = list(str1)
        lst2 = list(str2)
        result = []
        for i in range(len(lst1)):
            result.append(lst1[i])
            result.append(lst2[i])
        return ''.join(result)
    else:
        return …