如何使用anagrams彼此相邻的字符串数组进行排序

Question

如何使用彼此相邻的字谜对字符串数组进行排序？

例如:

输入{god,dog,abc,cab,man}
输出{abc,cab,dog,god,man}

我的方法:在O(nlogn)中对数组进行排序(不考虑anagrams情况).接下来,拾取第一个字符串并为字符串创建直方图,并将直方图与数组中剩余的字符串直方图进行比较,并将匹配的字符串放在数组的适当位置..重复,直到达到数组大小.此算法采用O(n ^ 3)的最坏情况(如果我们假设在最坏的情况下,每个字符串也是大小为n)和直方图表示的额外空间

直方图方法取自参考: 发现两个单词是否是彼此的字谜

我们能做得比这更好吗？

Answer 1

你当然可以做得更好,如下:

1. 循环遍历字符串数组
2. 对于每个字符串,首先对其字符进行排序,使用排序字符串作为键,将原始字符串作为值,放入哈希表中.你将得到一个哈希表,其中键是作为排序的字符串,值是所有的字谜,同时,这些值是有序的.您可以map<string, set<string> >用来为此目的服务.
3. 迭代哈希表并为给定的密钥输出所有字符串,它们应该彼此相邻

假设字符串的长度为M,并且数组的大小为N,则时间复杂度为:O(NMlogM),M通常平均小于N. 所以这比你说的要高效得多.