给定一个字符串数组,返回作为字谜的所有字符串组

Question

给定一个字符串数组,返回作为字谜的所有字符串组.

我的解决方案

对于数组中的每个字符串字,将其排序为O(m lg m),m是字的平均长度.

构建哈希表<string,list>.

将排序后的单词作为键放入哈希表中,并生成单词的所有排列(O(m!)),使用O(m)搜索字典中的每个排列(前缀树映射),如果它在字典中,将(O(1))放入哈希表中,以便将所有排列的单词放入具有相同键的列表中.

总共有O(n*m*lg m*m!)时间和O(n*m!)空间,n是给定数组的大小.

如果m非常大,那就没有效率了,m!.

更好的解决方案？

谢谢

Answer 1

我们定义一个字母表,其中包含我们的单词列表中可能包含的每个字母.接下来,我们需要为字母表中的每个字母使用不同的素数,我建议使用您能找到的最小字母.

这将给我们以下映射:{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有一个编程挑战:给定一个混乱的单词,在字典中查找它,看它是否在字典中的任何字谜.有一篇关于这个问题的有效解决方案的文章,我借用了答案,还详细介绍了进一步的优化问题.

Answer 2

使用计数排序对单词进行排序，这样排序可以在 O(m) 内完成。排序后从单词生成键并将节点（键，值）插入到哈希表中。生成密钥可以在 O(m) 内完成。

您可以将 (key,value) 中的值作为一些可以容纳多个字符串的动态数组。每次插入已经存在的键时，只需将生成键的原始单词推送到值数组上。

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