给定一个字符串数组，返回所有字符串组的字符串

给定一个字符串数组，返回所有字符串组的字符串。给定一个字符串数组，返回所有字符串组的字符串

我的解决方案：

对于阵列中的每个串字，排序它O（米LG米）中，m是一个字的平均长度。

建立一个散列表< string，list>。

将已排序的单词放入散列表中作为键，并且还生成单词的所有排列（O（m！）），用O（m）搜索字典（前缀树映射）中的每个排列，如果它在字典中，将它（O（1））放入散列表中，以便所有置换的单词都用相同的键放入列表中。完全地，O（n * m * lg m * m！）时间和O（n * m！）空间，n是给定数组的大小。

如果m非常大，效率不高，m！。

任何更好的解决方案？

感谢

来源

2011-12-16 user1002288

使用计数排序到字排序，以便排序可以在O（M）来实现。排序后生成密钥，并将节点（键，值）插入散列表。生成密钥可以在O（m）中实现。

您可以将（key，value）中的值作为一个可以容纳多个字符串的动态数组。每次插入已存在的密钥时，只需将值从数组中生成密钥的原始单词按下即可。

因此总体时间复杂度O（mn）其中n是单词总数（输入大小）。

而且这个环节有解决类似problems-> http://yourbitsandbytes.com/viewtopic.php?f=10&t=42

来源

2011-12-16 19:15:21 Ameliorator

我们定义了一个字母，其中包含每一封信我们可以在我们的单词表。接下来，我们需要为字母表中的每个字母使用不同的素数，我建议使用您可以找到的最小的字母。

这将使我们下面的映射： {A => 2，B => 3，C => 5，d => 7，等}

现在算在你想要的单词的字母表示与整数，并建立您的结果整数，如下所示：

伪代码：

result = 1 
for each letter: 
....result *= power(prime[letter], count(letter,word)

一些例子：

AAAA => 2^4

aabb => 2^2 * 3^2 = bbaa = baba = ...

等等。

因此，您将有一个整数来表示字典中的每个单词，并且要检查的单词将能够转换为整数。所以如果n是你的单词表的大小，并且k是最长单词的大小，那么将需要O（nk）来建立你的新词典，O（k）来检查一个新单词。

Hackthissite.com面临的编程挑战是：给定一个混乱的单词，在字典中查看它是否有任何字典在字典中。有一个有效的解决方案good article我从中借鉴了答案，它还详细讨论了进一步的优化。

来源

2011-12-16 19:20:06 silleknarf

我们还应该考虑构建字母表O（sizeof（字典）* k）的成本。在你的解决方案中，O（nk）是给定的字符串数组，而不是字典。谢谢 – user1002288 2011-12-16 20:12:31

是的，我应该已经更清楚了，n是字典的大小，你给的字符串数组可能是l，然后运行时O（lk）字典一旦建成 – silleknarf 2011-12-16 20:27:19

#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分析更好的人比我弄清楚复杂性。

来源

2011-12-16 19:30:00

将字典转换为映射到这些字符的每个字的单词的排序字符的映射并将其存储。对于每个给定的单词，对其进行排序，并将映射中的anagrams列表添加到输出中。

来源

2011-12-16 21:47:01 Paddy3118

我不相信你可以比

排序每个字
的字母排序
每一组的字谜现在将连续分组排序的单词列表做的更好为O方面。

来源

2011-12-16 22:03:22 Rafe

给定一个字符串数组，返回所有字符串组的字符串

回答

相关问题