给定一个字符串数组，返回所有的字符串组是anagrams [英] Given a string array， return all groups of strings that are anagrams

问题描述

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

我的解决方案：

对于数组中的每个字符串字，排序它O（m lg m），m是字的平均长度。

建立一个散列表<字符串，列表>。

将排序的字放入哈希表作为键，并生成该字的所有排列（O（m！）），搜索每个排列具有O（m）的字典（前缀树映射），如果它在字典中，则将其（O（1））放入哈希表中，使得所有改变的字用相同的键被放入列表中。 p>

总之，O（n * m * lg m * m！）时间和O（n * m！）空间，n是给定数组的大小。 >

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

任何更好的解决方案？

感谢

解决方案

我们定义一个字母表，我们可能在我们的wordlist。接下来，我们需要为字母表中的每个字母使用不同的素数，我建议使用您可以找到的最小的。

这将给我们以下映射：
{a => 2，b => 3，c => 5，d => 7，等}

表示为整数，并构建您的结果整数如下：

伪代码：

  result = 1 
 for each letters：
 .... result * = power（prime [letter]，count（letter，word）
  / pre> 
 
 
一些例子：
 
 
 
 aaaa => 2 ^ 4 
 
 
 
 aabb => 2 ^ 2 * 3 ^ 2 = bbaa = baba = ... 
 
 
 
等等。
 
 
 
所以你会有一个整数代表你的字典中的每个单词，你想要检查的单词将能够转换为一个整数，所以如果n是你的单词列表的大小，k是
 
 
 
 Hackthissite.com有一个编程挑战这是：给定一个乱码，查找它在字典中查看它是否有任何anagrams它是在字典中。有一个关于有效解决问题的好文章，我从中借来了答案，它也进入进一步优化的细节。 
 
Given a string array， return all groups of strings that are anagrams.

My solutions: 

For each string word in the array, sort it O(m lg m), m is the average length of a word. 

Build up a hash Table < string, list >.

Put the sorted word  into the hash table as key and also generate all permutations (O(m!)) of the word, search each permutation in a dictionary (a prefix tree map) with O(m), if it is in the dictionary, put (O(1)) it into the hash table so that all permutated words are put into the list with the same key.

Totally, O(n * m * lg m *  m!) time and O(n* m!) space , n is the size of the given array.

If m is very large, it is not efficient , m! . 

Any better solutions  ? 

thanks
解决方案
We define an alphabet, which contains every letter we may have in our wordlist. Next, we need a different prime for each of the letters in the alphabet, I recommend using the smallest you can find.

That would give us the following mapping:
{ a => 2, b => 3, c => 5, d => 7, etc }

Now count the letters in the word you want to represent as integer, and build your result integer as follows:

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

aaaa => 2^4

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

and so on.

So you will have an integer representing each word in your dictionary and the word you want to check will be able to be converted to an integer. So if n is the size of your wordlist and k is the size of the longest word it will take O(nk) to build your new dictionary and O(k) to check a new word.

Hackthissite.com has a programming challenge which is: Given a scrambled word, look it up in a dictionary to see if any anagrams of it are in the dictionary. There is a good article on an efficient solution to the problem from which I have borrowed the answer, it also goes into detail on further optimisations. 

                        
这篇关于给定一个字符串数组，返回所有的字符串组是anagrams的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！