查找给定单词的字谜

小编典典

查找给定单词的字谜

algorithm

如果两个单词中的一个具有与另一个单词完全相同的字符，则它们是字谜。

范例：Anagram＆Nagaram是字谜（不区分大小写）。

现在有很多与此类似的问题。查找两个字符串是否为字谜的两种方法是：

1） Sort将字符串进行比较。

2）frequency map为这些字符串创建一个，然后检查它们是否相同。

但是在这种情况下，我们得到一个单词（为简单起见，我们仅假设一个单词，并且只包含单个单词的字谜），我们需要为此找到一个字谜。

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

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

我也在类似的线程中读到可以使用某些东西来完成工作，Tries但是该人员没有解释算法是什么以及为什么我们首先使用Trie，只是在Python或Ruby中提供了一个实现。所以那并没有真正的帮助，这就是为什么我创建了这个新线程。如果有人要共享其实现（C，C
++或Java除外），请也进行解释。

阅读 270

2020-07-28

共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

建立起来比较快，查找起来非常快。

2020-07-28