给定一个字符串数组,返回作为字谜的所有字符串组.
我的解决方案
对于数组中的每个字符串字,将其排序为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等}
现在计算要表示为整数的单词中的字母,并按如下方式构建结果整数：
伪代码：
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,我已经借用了答案,它还详细介绍了进一步的优化.
