string - 如何在文件中给出的单词中查找字谜

Question

如何在文件中给出的单词中查找变位词。

我的解决方案:

对它们进行排序，然后查找重复项。

O(n mlgm)。 n:单词数，m:单词的最大大小

有更好的解决方案吗？

谢谢

Answer 1

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

Any integer greater than 1 is either a prime number, or can be written as a unique product of prime numbers (ignoring the order).

这是代码。我将单词转换为大写，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;
}

此处提供完整说明: Anagram on dev.vvirlan.com