如何查找在文件中给出的单词之间的字谜

Question

如何查找在文件中给出的单词之间的字谜.

我的解决方案

对它们进行排序然后找到重复项.

O(n mlgm).n:单词数,m:单词的最大大小

更好的解决方案？

谢谢

Answer 1

这是一个没有排序的解决方案: 我想出了一个新的解决方案.它使用算术的基本定理.所以我的想法是使用前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;
}

完整的描述可在此处获取: dev.vvirlan.com上的Anagram

Answer 2

使用在单词的排列下不变的散列函数来散列所有单词,例如计算每个字母的频率计数并散列该数组.将它们放在哈希表中并查找散列到相同值的条目(当然,由于哈希表的性质,您仍然必须测试这些冲突是否是实际的字谜).

这应该在O(n)时间内运行,假设您选择了一个好的哈希函数并且您的输入集不包含太多的字谜(在最坏的情况下,如果每个字都是每个其他字的字谜,则在O(n)中运行²)时间).