Algorithm Question On Finding All Valid Words In Dictionary

Question

Given a dictionary (just a list of strings).

You receive a feed of an unknown number of letters from an external source. Given the string of letters, how would you go about listing all valid words (from the diciontary) you can make from any combination from those letters.

So if you receive: abpplead

You should find apple, bad, pad, lead, etc.

I know there's no best answer. But what are some reasonably efficient ways to do it, what data structures to use, etc.

Also, assume you can pre-process the input, so you can choose to store the input letters as they come in in whatever data structure you want.

Answer 1

Put the dictionary into a trie. Then put the letters into an counter array indexed by their character values, maintaining the counts for each letter (let call this counts[]). Then traverse the trie in depth first search order, decrementing the counts[letter] value for each letter while traversing downward, and incrementing it on the way back up. Now, any time a counts[letter] is about to go negative, stop and traverse back upwards. Any time you reach a word terminator, output the result.