algorithm - 在一组字符串上查找输入的字谜..？

Question

给定一组字符串(大集合)和一个输入字符串，您需要有效地找到输入字符串的所有变位词。你将使用什么数据结构。使用它，您将如何找到字谜？

我想到的是这些:

1. 使用 map

   a) 消除所有字母比输入多/少的单词。

   b) 将输入的字符放入map中

   c) 遍历每个字符串的映射并查看是否所有字母都存在并带有它们的计数。

2. 使用尝试

   a) 将所有具有正确字符数的字符串放入一个 trie 中。

   b) 遍历每个分支，如果字母包含在输入中则继续深入。

   c) 如果叶子到达这个词是一个变位词

谁能找到更好的解决方案？

您发现上述方法有什么问题吗？

Answer 1

从每个单词构建频率图并比较这些图。

伪代码:

class Word

  string word
  map<char, int> frequency

  Word(string w)
    word = w
    for char in word
      int count = frequency.get(char)
      if count == null
        count = 0
      count++
      frequency.put(char, count)

  boolean is_anagram_of(that)
    return this.frequency == that.frequency