8

来源：微软面试题

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

有人可以建议最佳算法来做到这一点。

我知道的唯一方法是 对所有单词进行排序，然后检查。

4

4 回答 4

15

在建议算法之前了解更多关于数据的信息会很好，但我们假设在单一情况下单词是英文的。

让我们为每个字母分配一个从 2 到 101 的素数。对于每个单词，我们可以通过将其字母对应的数字相乘来计算它的“字谜数字”。

让我们声明一个 {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

当然可以进一步优化实现。例如，您实际上并不需要字谜图，只需一个计数器就可以了。但我想代码最好地说明了这个想法。

于 2013-06-01T12:23:46.167 回答
3

您可以使用“Tries”。 Trie（源自检索）是一种多路搜索树。尝试使用模式匹配算法。它的基本用途是创建拼写检查程序，但我认为它可以帮助你的情况..看看这个链接http://ww0.java4.datastructures.net/handouts/Tries.pdf

于 2013-06-01T12:28:05.220 回答
2

不久前，我以不同的方式做了这个。

  1. 将文件内容拆分为单词数组
  2. 创建一个将键字符串映射到字符串链表的 HashMap
  3. 对于数组中的每个单词，对单词中的字母进行排序并将其用作字谜链表的键

public static void allAnagrams2(String s) { String[] input = s.toLowerCase().replaceAll("[^az^\s]", "").split("\s"); 哈希映射> hm = 新哈希映射>();

    for (int i = 0; i < input.length; i++) {
        String current = input[i];

        char[] chars = current.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);

        LinkedList<String> ll = hm.containsKey(key) ? hm.get(key) : new LinkedList<String>();
        ll.add(current);

        if (!hm.containsKey(key))
            hm.put(key, ll);
    }
}
于 2013-11-12T00:19:06.360 回答
0

与上述方法略有不同。而是返回一个字谜的哈希图。

Public static Hashmap<String> anagrams(String [] list){

    Hashmap<String, String> hm = new Hashmap<String, String>();
    Hashmap<String> anagrams = new Hashmap<String>();

    for (int i=0;i<list.length;i++){
        char[] chars = list[i].toCharArray();
        Arrays.sort(chars);
        String k = chars.toString();
        if(hm.containsKey(k)){
            anagrams.put(k);
            anagrams.put(hm.get(k));
        }else{
            hm.put(k, list[i]); 
        }
    }
}
于 2014-01-16T07:14:15.977 回答