问题描述
我正在尝试编写一个程序，将所有字谜组合在一个列表中，并且输出必须按字母顺序排序。我已经有一个按字母顺序对输入进行排序的程序，它使用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...