Re: find words that contains some specific letters
Giovanni Azua wrote:
One word lookup in the Set costs O(log m) binary search and not O(1).
That is incorrect for HashSet, assuming you mean 'm' to be the set
size.
Therefore the O(log m) is *for each* generated permutation, and this is w=
hy
the multiplication i.e. [sic] O(n! * log m)
According to Sun's documentation for HashSet:
This class offers constant time performance for the basic operations
(add, remove, contains and size), assuming the hash function disperses
the elements properly among the buckets.
The term "constant time" means O(1). Therefore the lookup time is O
(1) for each generated permutation, and this is why the multiplication
is O(n! * 1 ).
Likewise, one word lookup in a HashMap <String, Set<String>> is O(1).
If you use only a single permutation to do the lookup, i.e., the
alphabetically sorted one, then you only do a single lookup for a
HashMap, not n! lookups.
Or one build the dictionary as a Map indexed by word letters in
alphabetical order with the values being corresponding Sets of words us=
ing
those letters. Then you only do an O(1) lookup into the Map to find the
single ordered permutation of the search term, then return the matching
Set directly. So now the overall lookup complexity is that of sortin=
g the
letters in the search term.
I was writing meantime a similar algorithm to this one you explain ... yo=
u
have to watch for multiple occurrences of the same letter though and the =
Set
should be SortedSet so there is calculating intercept of the Sets which i=
s
O(n) if the Sets are SortedSet.
The OP asked to find "all words in a dictionary that contains some
specific set of letters. ... containing the exact letters ..." If you
implement their "set of letters" as a String containing the letters in
alphabetic order, then you can include duplicated letters as part of
the search term. You wouldn't want a SortedSet to be the dictionary;
a Map is better, specifically a HashMap<String, Set<String>>. You do
an O(1) lookup of the search term, that is, a String comprising the
search letters in order, and get back the Set of matching words in a
single get().
Wouldn't you agree that the O(1) algorithm is a better choice than an O
(n) one?
--
Lew