给定一个字符串数组，返回所有的字谜字符串组。
我的解决方案：
对于数组中的每个字符串单词，对其进行排序 O(m lg m)，m 是一个单词的平均长度。
建立一个哈希表<字符串，列表>。
将排序后的词作为键放入哈希表中，同时生成该词的所有排列（O（m！）），用 O（m）在字典（前缀树映射）中搜索每个排列，如果它在字典中, 将 (O(1)) 放入哈希表中，以便所有置换后的单词都放入具有相同键的列表中。
总共有 O(n * m * lg m * m!) 时间和 O(n* m!) 空间，n 是给定数组的大小。
如果 m 很大，则效率不高，m！.
有更好的解决方案吗？
谢谢
我们定义了一个字母表，其中包含我们单词表中可能拥有的每个字母。接下来，我们需要为字母表中的每个字母使用不同的素数，我建议使用你能找到的最小的。
这将为我们提供以下映射：{ a => 2, b => 3, c => 5, d => 7, etc }
现在将要表示的单词中的字母数为整数，并按如下方式构建结果整数：
伪代码：
result = 1
for each letter:
....result *= power(prime[letter], count(letter,word)
一些例子：
aaa => 2^4
aabb => 2^2 * 3^2 = bbaa = baba = ...
等等。
因此，您将有一个整数表示字典中的每个单词，并且您要检查的单词将能够转换为整数。因此，如果 n 是您的单词列表的大小，k 是最长单词的大小，则构建新词典需要 O(nk) 时间，检查新单词需要 O(k) 时间。
Hackthissite.com 有一个编程挑战是：给定一个打乱的单词，在字典中查找它，看看它的任何字谜是否在字典中。有一篇关于有效解决问题的好文章，我从中借用了答案，它还详细介绍了进一步的优化。
使用计数排序对单词进行排序，以便在 O(m) 中完成排序。排序后从单词生成键并将节点（键，值）插入哈希表。生成密钥可以在 O(m) 内完成。
您可以将 (key,value) 中的值作为一些可以容纳多个字符串的动态数组。每次插入已经存在的键时，只需在值数组上推送生成键的原始单词。
所以总体时间复杂度 O(mn) 其中 n 是单词的总数（输入的大小）。
此链接也解决了类似问题-> http://yourbitsandbytes.com/viewtopic.php?f=10&t=42
#include <map>
#include <iostream>
#include <set>
#include <algorithm>
int main () {
std::string word;
std::map<std::string, std::set<std::string>> anagrams;
while(std::cin >> word) {
std::string sortedWord(word);
std::sort(sortedWord.begin(), sortedWord.end());
anagrams[sortedWord].insert(word);
}
for(auto& pair : anagrams) {
for(auto& word : pair.second) {
std::cout << word << " ";
}
std::cout << "\n";
}
}
我会让比我更擅长大 O 分析的人弄清楚复杂性。
将字典转换为一个单词的排序字符的映射，该映射映射到这些字符的每个单词并存储它。对于给定的每个单词，对其进行排序并将映射中的字谜列表添加到您的输出中。
我不相信你可以在 O 方面做得比