Algorithm for word matching [closed]

Question

My main idea is to find an algorithm ( Java ) that takes the random letters which someone has typed in a JoptionPane for instance and then instantly by pressing "Find words" i would like the program to derive all those words that match my letters from a dictionary stored in a .txt file.

I am struggling to find that algorithm.

For example:

Take into consideration that we got the following letters in a Scrabble match:

a , o ,p, t, e, z, e, w

I would like to find a java code or at least an algorithm in order to find from an english dictionary .txt file all the words that have those letters but not anything else. if I type " a, p, p" I want to have as a result the word "app" and not (app"s"). So ... to sum up, how can i compare those letters from words stored in a .txt file and as a result get specific words that match in my given letters ?

Answer 1

There are different ways to do this, depending on how efficient you want it.

An easy but less efficient way is, to take the string and go through the whole dictionary-file, checking each line if the requirement is met: checking for each character of the input whether it is present in the dict-file-line (make a temp-copy of it and remove chars from it so that each available letter can only be used once).

A harder but efficient way is, to pre-process the dictionary-file into a Trie (Prefix-Tree) [wikipedia]. You can then use all permutations of the input-string as a roadmap through the Trie.

EDIT: note as Marko Topolnik points out that computing all permutations of the input-string would be expensive - so to avoid that: at every step you only check which letters are still available from the input-string AND of those you only keep which are available as next-branches in the Trie.