algorithm - 查找给定单词的字谜

Question

如果其中一个单词的字符与另一个单词的字符完全相同，那么这两个单词就是变位词。

示例:Anagram & Nagaram 是变位词(不区分大小写)。

现在类似这样的问题很多。查找两个字符串是否为变位词的几种方法是:

1) 排序字符串并进行比较。

2)为这些字符串创建一个频率图并检查它们是否相同。

但在这种情况下，我们得到了一个单词(为了简单起见，让我们假设只有一个单词，它只会有单个单词的变位词)，我们需要为此找到变位词。

我想到的解决方案是，我们可以为单词生成所有排列，并检查这些单词中哪些存在于字典中。但显然，这是非常低效的。是的，字典也可用。

那么我们这里有什么选择呢？

我也在一个类似的线程中读到，可以使用 Tries 来完成一些事情，但是那个人没有解释算法是什么以及为什么我们首先使用 Trie，只是一个在 Python 或 Ruby 中也提供了实现。所以这并没有真正帮助，这就是我创建这个新线程的原因。如果有人想分享他们的实现(C、C++ 或 Java 除外)，请也请解释一下。

Answer 1

示例算法:

Open dictionary
Create empty hashmap H
For each word in dictionary:
  Create a key that is the word's letters sorted alphabetically (and forced to one case)
  Add the word to the list of words accessed by the hash key in H

检查给定单词的所有字谜:

Create a key that is the letters of the word, sorted (and forced to one case)
Look up that key in H
You now have a list of all anagrams

构建速度相对较快，查找速度极快。