l*********y
发帖数: 142 | 1 given a Collection words, return a Collection of anagrams
found in the given collection for example "The rat fell in the tar" =>
returned [rat tar]
Requirement:
O(n k lg k) where n is the number of words and k is the average length of
the word
sorting is O(n k lg k) , then in order to how all anagrams, how to make it
under
O(n k lg k) ?
Thanks! | g*********s
发帖数: 1782 | 2
anagrams
why "the", "fell" not in the collection? so single occurrences are
excluded?
of
it
【在 l*********y 的大作中提到】
: given a Collection words, return a Collection of anagrams
: found in the given collection for example "The rat fell in the tar" =>
: returned [rat tar]
: Requirement:
: O(n k lg k) where n is the number of words and k is the average length of
: the word
: sorting is O(n k lg k) , then in order to how all anagrams, how to make it
: under
: O(n k lg k) ?
: Thanks!
| l*********y
发帖数: 142 | 3
The question wants to find all pairs of anagrams.
【在 g*********s 的大作中提到】
:
: anagrams
: why "the", "fell" not in the collection? so single occurrences are
: excluded?
: of
: it
| a******7
发帖数: 106 | 4 use hash table, map each character to a primer number, and therefore each
word to sum, then it can be finished in O(n*k) | g*********s
发帖数: 1782 | 5 what do "all pairs" mean? say, if u have abc, bca, cab, then there are
totally 3 pairs...
【在 l*********y 的大作中提到】
:
: The question wants to find all pairs of anagrams.
| l*****a
发帖数: 14598 | 6 你是要返回collection>的
否则多个怎么办？
anagrams
of
it
【在 l*********y 的大作中提到】
: given a Collection words, return a Collection of anagrams
: found in the given collection for example "The rat fell in the tar" =>
: returned [rat tar]
: Requirement:
: O(n k lg k) where n is the number of words and k is the average length of
: the word
: sorting is O(n k lg k) , then in order to how all anagrams, how to make it
: under
: O(n k lg k) ?
: Thanks!
| l*********y
发帖数: 142 | 7
The question is not originally from me, but I guess triplet should be
considered as
one set of anagrams.
anson627
use hash table, map each character to a primer number, and therefore each
word to sum, then it can be finished in O(n*k)
is it easy to implement this idea on white board?
How to store the product of prime number? If it is a large number, I think
it is linear to the size of character. Then the multiplication takes k^2
time.
【在 g*********s 的大作中提到】
: what do "all pairs" mean? say, if u have abc, bca, cab, then there are
: totally 3 pairs...
| j*****u
发帖数: 1133 | 8 use a hash table: Dictionary>
where key is sorted string, value is all strings equal to key after sorting
1st go thru all words, sort them and insert into the hash table
then go thru each value of hash table which contains the anagrams
【在 l*********y 的大作中提到】
:
: The question is not originally from me, but I guess triplet should be
: considered as
: one set of anagrams.
: anson627
: use hash table, map each character to a primer number, and therefore each
: word to sum, then it can be finished in O(n*k)
: is it easy to implement this idea on white board?
: How to store the product of prime number? If it is a large number, I think
: it is linear to the size of character. Then the multiplication takes k^2
|
|
