为给定单词找到anagrams
如果其中一个字与另一个字的字符完全相同，则两个字是anagrams。
示例： Anagram和Nagaram是anagrams（不区分大小写）。
现在有很多类似的问题。 找出两个字符串是否是anagrams的一些方法是：
1）对字符串进行Sort并进行比较。
2）为这些字符串创建一个frequency map并检查它们是否相同。
但在这种情况下，我们给了一个词（为了简单起见，我们只假设一个词，它将只有一个单词词），我们需要为此找到一个词。
我想到的解决方案是，我们可以为单词生成所有排列 ，并检查字典中存在哪些单词 。 但显然，这是非常低效的。 是的，字典也可用。
那么我们在这里有什么替代方案？
我也在类似的线程中读到了使用Tries可以完成的事情，但是这个人并没有解释算法是什么，为什么我们首先使用了Trie，只是在Python或Ruby中也提供了一个实现。 所以这不是很有用，这就是为什么我创建了这个新线程。 如果有人想分享他们的实现（除C，C ++或Java之外），请善意解释它。
算法示例：
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
查找速度快，构建速度快。
我想出了一个新的解决方案。 它使用算术的基本定理。 所以想法是使用前26个素数的数组。 然后，对于输入词中的每个字母，我们得到相应的素数A = 2，B = 3，C = 5，D = 7 ...，然后我们计算输入词的乘积。 接下来，我们为字典中的每个单词执行此操作，并且如果一个单词与我们的输入单词相匹配，则将其添加到结果列表中。 所有的anagrams将具有相同的签名，因为
任何大于1的整数都是质数，或者可以写为质数的唯一乘积（忽略顺序）。
这是代码。 我把这个词转换成大写字母，而65是A的位置，它对应于我的第一个素数：
private int[] PRIMES = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,
37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103,
107, 109, 113 };
这是方法：
private long calculateProduct(char[] letters) {
long result = 1L;
for (char c : letters) {
if (c < 65) {
return -1;
}
int pos = c - 65;
result *= PRIMES[pos];
}
return result;
}
我们知道，如果两个单词的长度不相同，它们不是字谜。 所以你可以把你的字典分成长度相同的单词组。
现在我们只关注这些小组中的一个，基本上所有的单词在这个较小的宇宙中具有完全相同的长度。
如果每个字母位置是一个维度，并且该维度中的值基于该字母（例如ASCII码）。 然后你可以计算单词向量的长度。
例如，说'A'= 65，'B'= 66，然后length("AB") = sqrt(65*65 + 66*66) 。 显然， length("AB") = length("BA") 。
显然，如果两个词是anagrams，那么它们的向量具有相同的长度。 接下来的问题是，如果两个字（相同数量的字母）矢量具有相同的长度，他们是否是字谜？ 直觉上，我会说不，因为所有具有这种长度的向量形成一个球体，所以有很多。 不确定，因为在这种情况下我们在整数空间中，实际上有多少个。
但至少它可以让你进一步分割字典。 对于字典中的每个单词，计算向量的距离： for(each letter c) { distance += c*c }; distance = sqrt(distance); for(each letter c) { distance += c*c }; distance = sqrt(distance);
然后为长度为n所有单词创建一个映射，并用距离键入它，该值是长度为n的单词列表，该列表产生该特定距离。
您将为每个距离创建一张地图。
然后你的查找成为以下算法：