文件中的所有字谜

Question

来源:微软访谈问题

我们得到一个包含单词的文件.我们需要确定其中存在的所有Anagrams.

有人可以建议最优化的算法来做到这一点.

我知道的唯一方法是 排序所有单词,然后检查.

Answer 1

在建议算法之前了解有关数据的更多信息会很好,但我们假设单个案例中的单词是英文的.

让我们为每个字母分配一个从2到101的素数.对于每个单词,我们可以通过乘以其字母对应的数字来计算它的"anagram数字".

让我们声明一个{number,list}对的字典.还有一个列表可以收集产生的字谜.

然后我们可以分两步收集字谜:简单地遍历文件并根据其"字谜数字"将每个单词放入字典列表中; 遍历地图,对于长度超过1的每个对列表,将其内容存储在单个大的字谜列表中.

更新:

import operator

words = ["thore", "ganamar", "notanagram", "anagram", "other"]

letter_code = {'a':2, 'b':3, 'c':5, 'd':7, 'e':11, 'f':13, 'g':17, 'h':19, 'i':23, 'j':29, 'k':31, 'l':37, 'm':41, 'n':43, 
            'o':47, 'p':53, 'q':59, 'r':61, 's':67, 't':71, 'u':73, 'v':79, 'w':83, 'x':89, 'y':97, 'z':101}

def evaluate(word):
    return reduce( operator.mul, [letter_code[letter] for letter in word] )

anagram_map = {}
anagram_list = []
for word in words:
    anagram_number = evaluate(word)
    if anagram_number in anagram_map:
        anagram_map[ anagram_number ] += [word]
    else:
        anagram_map[ anagram_number ] = [word]

    if len(anagram_map[ anagram_number ]) == 2:
        anagram_list += anagram_map[ anagram_number ] 
    elif len(anagram_map[ anagram_number ]) > 2:
        anagram_list += [ word ]

print anagram_list

当然,可以进一步优化实现.例如,你真的不需要一个字谜地图,只需一个计数器就行了.但我想这段代码最好地说明了这个想法.