时间戳

首页 > 解决方案 > 减少 Anagram 词搜索的计算时间

python - 减少 Anagram 词搜索的计算时间

问题描述

下面的代码是搜索单词列表并创建任何字谜的子列表的蛮力方法。

搜索整个英语词典非常耗时，所以我很好奇有人有降低代码计算复杂度的技巧吗？

def anogramtastic(anagrms):
    d = []
    e = []
    for j in range(len(anagrms)):
        if anagrms[j] in e:
            pass
        else:
            templist = []
            tester = anagrms[j]        
            tester = list(tester)
            tester.sort()
            tester = ''.join(tester)
            for k in range(len(anagrms)):
                if k == j:
                    pass
                else:
                    testers = anagrms[k]        
                    testers = list(testers)
                    testers.sort()
                    testers = ''.join(testers)
                    if testers == tester:
                        templist.append(anagrms[k])
                        e.append(anagrms[k])
            if len(templist) > 0:
                templist.append(anagrms[j])
                d.append(templist)
    d.sort(key=len,reverse=True) 
    return d

print(anogramtastic(wordlist))

标签： python

解决方案

使用frozensets字典怎么样？Frozensets 是不可变的，这意味着您可以散列它们以进行持续查找。当谈到字谜时，使两个单词彼此字谜的原因是它们具有相同的字母和相同的计数。因此，您可以构造一组 {(letter, count), ...} 对的冻结集，并对它们进行哈希处理以进行有效查找。

这是一个快速的小功能，可以使用以下方法将单词转换为多重集collections.Counter：

from collections import Counter, defaultdict

def word2multiset(word):
    return frozenset(Counter(word).items())

现在，给定一个单词列表，像这样填充你的字谜字典：

list_of_words = [... ]

anagram_dict = defaultdict(set)
for word in list_of_words:
    anagram_dict[word2multiset(word)].add(word)

例如， when list_of_words = ['hello', 'olleh', 'test', 'apple']，这是anagram_dict上面循环运行后的输出：

print(anagram_dict)
defaultdict(set,
            {frozenset({('e', 1), ('h', 1), ('l', 2), ('o', 1)}): {'hello',
              'olleh'},
             frozenset({('e', 1), ('s', 1), ('t', 2)}): {'test'},
             frozenset({('a', 1), ('e', 1), ('l', 1), ('p', 2)}): {'apple'}})

推荐阅读