高效地将字谜分组 [英] Grouping anagrams efficiently

问题描述

我正在尝试编写一个程序，将所有字谜组合在一个列表中，并且输出必须按字母顺序排序。我已经有一个按字母顺序对输入进行排序的程序，它使用heapsort在O(nlog(N))时间内完成。我的程序也对字谜进行分组，但是速度太慢了。我相信使用散列会给出一个有效的算法，但不太确定如何实现它。有没有人对完成这项任务的高效算法有什么建议？

输入：

eat tea tan ate nat bat

输出：

ate eat tea

bat

nat tan

推荐答案

是的，哈希是。

您可以使用以下散列技术：(假设您的字符串都没有空格并且只有小写字符，如果它们是大写字符，则会得到不同的处理(那么CAT和Act就不是字谜))

字符的哈希值将是其ascii值的平方，即。

a = 97*97, b = 98*98, etc.

将每个单词中的字符值相加，这将是其哈希值。

现在，使用相同(相等)的哈希值将单词分组在一起。

ps：如果cat和Act是字谜，请在计算前将A转换为a。

PPS：为了回应@Amit的评论，我平方了每个字符的ASCII值以减少冲突，但这并不是绝对没有冲突。您可以使用第n^斐波纳契数的平方作为散列值，然后将它们相加。这进一步减少了碰撞。 因此，哈希值将如下所示：

a = 98^2, b = 99^2, c = (98+99)^2, d = (b+c)^2 and so on...

这篇关于高效地将字谜分组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！