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

Question

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

例如:

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

我的方法: 在 O(nlogn) 中对数组进行排序(不考虑变位词的情况)。下一个， 拿起第一个字符串并为该字符串创建一个直方图，并将该直方图与数组中其余字符串的直方图进行比较，并将匹配的字符串放在数组的适当位置..重复直到它达到数组大小..这个算法最差O(n^3) 的情况(如果我们假设在最坏的情况下，每个字符串的大小也是 n)和直方图表示的额外空间

取自引用的直方图方法: finding if two words are anagrams of each other

我们能做得更好吗？

Answer 1

你当然可以做得更好:

1. 遍历字符串数组
2. 对于每个字符串，首先对它的字符进行排序，使用排序后的字符串 作为键和原始字符串作为值，放入哈希表中。你最终会得到一个哈希表 键是排序的字符串，值都是变位词，同时，这些值是有序的。您可以使用 map<string, set<string> >为此目的服务。
3. 遍历哈希表并输出所有的变位词 给定 key ，它们应该彼此相邻

假设字符串长度为M，数组大小为N 则时间复杂度为:O(NMlogM)，M通常平均小于N。所以这比你说的更有效率。