查找给定单词的字谜

Question

如果其中一个字符与另一个字的字符完全相同,则两个字是字谜.

示例:Anagram&Nagaram是anagrams(不区分大小写).

现在有很多类似的问题.找出两个字符串是否为字谜的几种方法是:

1) Sort字符串并比较它们.

2)frequency map为这些字符串创建一个并检查它们是否相同.

但是在这种情况下,我们会给出一个词(为了简单起见,我们只假设一个单词,它只有单个单词anagrams),我们需要找到它的字谜.

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

那么我们有什么替代方案呢？

我也在一个类似的线程中读到可以使用的东西,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

构建速度相对较快,查找速度极快.

Answer 2

我猜想我想出了一个新的解决方案.它使用算术的基本定理.所以我的想法是使用前26个素数的数组.然后对于输入字中的每个字母,我们得到相应的素数A = 2,B = 3,C = 5,D = 7 ......然后我们计算输入字的乘积.接下来,我们对字典中的每个单词执行此操作,如果单词与输入单词匹配,则将其添加到结果列表中.所有的字谜都有相同的签名,因为

任何大于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;
}