分组字谜 [英] Grouping anagrams

问题描述

考虑的话，组字谜数组 IP：{焦油，大鼠，香蕉，ATR} OP：{[焦油，大鼠，ATR]，[香蕉]}

Given array of words, group the anagrams IP:{tar,rat,banana,atr} OP:{[tar,rat,atr],[banana]}

一个解决方案，以使用哈希表这个问题。考虑每一个字，排序并添加为重点，以哈希表，如果没有present。为密钥的值将是使用相同的密钥的所有字谜的列表。我想知道的时间复杂度，要在数组中的人物进行排序，假设为O（n log n）的要存储在哈希表中这将是为O（n），共有O（N * nlogn）。

One solution to this question using Hash Table. consider each word, sort it and add as key to hash table if not present. The value for the key would be a list of all anagrams with the same key. I wanted to know about the time complexities, To sort the characters in an array, suppose O(n log n) To store in the hash table it would be O(n), a total of O(n*nlogn).

有没有更好的算法？用较少的时间复杂度？

Is there a better algorithm? with lesser time complexity?

推荐答案

有关时间复杂度的缘故，你总是可以使用计数排序个人的话，其成本每字只是线性时间进行排序。也可以先计算的字母出现则散列的发生计数，而不是有序字样，这是基本相同数量的排序减去重建步骤

For time complexity's sake, you could always use counting sort to sort the individual words, which cost just linear time per word. You can also first count the occurrences of letters then hash the occurrences count instead of the sorted word, which is essentially the same as counting sort minus the rebuild step.

不过既然话通常很短，这可能不是你买什么实际的好处。

But since the words will typically be short, this might not buy you any practical advantages.

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