algorithm - 分组字谜

Question

给定单词数组，将字谜分组 IP:{tar,rat,banana,atr} OP:{[tar,rat,atr],[banana]}

使用哈希表解决此问题的一种方法。考虑每个单词，对其进行排序，如果不存在，则将其作为键添加到哈希表中。键的值将是具有相同键的所有字谜的列表。我想知道时间复杂度，要对数组中的字符进行排序，假设 O(n log n) 存储在哈希表中将是 O(n)，总共 O(n*nlogn)。

有更好的算法吗？时间复杂度更小？

Answer 1

出于时间复杂性的考虑，您始终可以使用计数排序来对单个单词进行排序，这仅花费每个单词的线性时间。您还可以先计算字母的出现次数，然后对出现次数进行哈希处理，而不是对已排序的单词进行哈希处理，这与计算排序减去重建步骤基本相同。

但由于单词通常很短，这可能不会给你带来任何实际优势。