Re: find words that contains some specific letters
On Jun 1, 10:12 am, "Giovanni Azua" <brave...@hotmail.com> wrote:
Ciao Fralentino,
"Fralentino" <bare...@gmail.com> wrote in message
Hi!
I want to make an algorithm that searches for all words in a
dictionary that contains some specific set of letters. For example i
want to find all words containing the exact letters t,a,s,m,p so the
word stamp is ok.
So basically i want to compare a String with a set of letters and find
out if you can build this string with these exact letter. I have a
solution for this but i dont think it's the the most optimal one so i
would like som tips on how do to this in a optimal and rather easy
way. Is there some recommended designs in how to do this? Is there
perhaps some method or class in the java api that does this for you?
I thought of a possible algorithm to resolve this problem without using
permutations btw I think you also have to take into account the case of
repeated letter occurrences. The idea would be to build a suitable struct=
ure
so the lookup time is the fastest.
You would build the following structure from your dictionary once:
Map<String, SortedSet<String>> this is a map of SortedSet of words in the
dictionary keyed by the letters they occur in, and the words in the
SortedSet are ordered alphabetically e.g.
map.get("a").contains("fall") == true
map.get("a").contains("aurora") == false
map.get("aa").contains("aurora") == true // resolves the issue of =
words
with repeated occurrences of a letter
The OP asked for words comprising the exact letters of the search
term, not merely including the searched letters.
Fralentino wrote:
basically i [sic] want to compare a String with a set of letters
and find out if you can build this string with these exact letter[s].
Thus, "aurora" would not be a valid match for "aa", although it would
be a match for "aaorru".
--
Lew