更优化的解决方案

Question

我有一个单词列表。我需要找到字谜并返回一组字谜列表例如：输入：['cat','act','dog','ogd']输出：[{'cat','act'}, {'dog','ogd'}]

我能够正确编码，但我需要一个更优化的替代解决方案。任何人都可以帮助我吗？

from collections import defaultdict 

def group(words):
    d = {}

    for word in words: 
        key = "".join(sorted(word))
        d.setdefault(key, set()).add(word)

    sets = list(d.values())

    return sets

我需要一个更优化的解决方案

Answer 1

Anagrams不关心秩序。考虑到这个事实时会想到集合。问题是集合不可清除并且不考虑重复，并且由于您不能使用散列，因此可能比较慢。

为了快速，此解决方案尝试避免排序并且更喜欢散列：

首先，我们创建一个快速哈希的函数：

import collections
def anagram_hash(word):
    return frozenset(collections.Counter(word).items())

然后我们使用defaultdict在单个go中快速聚合：

anagrams = collections.defaultdict(list)
for word in words:
    anagrams[anagram_hash(word)].append(word)