有效地分组字形

Question

我正在尝试编写一个程序，将所有字母组合在一起，并且输出必须按字母顺序排序。我已经有了一个程序来按字母排序输入，它使用heapsort在O（nlog（n））时间内完成输入。我的程序也分组了字谜，但它太慢了。我相信使用散列会给出一个有效的算法，但不太清楚如何实现它。有没有人有任何建议，有效的算法来完成这项任务？

例如。

输入：

eat tea tan ate nat bat 

输出：

ate eat tea 

bat 

nat tan 

Answer 1

似乎你看它是错误的。根据我的理解，您首先按字母顺序排序字符串，然后尝试将它们分组。

试着做相反的事。首先，将字符串分组为字符，然后才对每个分组进行排序。

分组字谜可以通过多种方式来完成，这里就是其中之一：

1. 排序每个字符串转换成字谜。这意味着，每个字谜本身都是排序的。例如：吃，茶，nat都将被分类为字符串“aet”。 （记住每个单词的原始形式以备后用）。
2. 一旦每个单词都是“anagram排序”，您可以简单地使用散列表将它们分组，所有这些都使用Map<String,List<String>> - 其中key是“排序的anagram”，并且该值是包含所有原始单词的列表。
3. 一旦你有了这张地图，你需要对每个列表进行排序，这个列表是这张地图上的一个值，这是你的最终输出。

Answer 2

是的，哈希是。 （假设你的字符串全部没有空格并且只有小写字符，并且如果它们有大写字母，它将被区别对待（cat和Act不是字典））

字符的散列值将是其ASCII值的平方，即。

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

将每个单词中的字符值相加，即它的散列值。

现在，将具有相同（相等）散列值的单词组合在一起。 PS：如果cat和act是anagrams，在计算之前将A转换为a。

PPS：为了回应@amit的评论，我对每个角色的ASCII值进行了平方以减少碰撞，但是，这不会是完全无碰撞的。您可以使用第n个斐波纳契数的平方作为散列值，然后添加它们。这进一步减少了碰撞。 因此，散列值将如下所示：

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