Java – algorithm problem of finding all valid words in the dictionary

Given a dictionary (just a list of strings)

You have received an unknown number of letters from an external source Given a string of letters, how would you list all valid words (from diciontary) that you can make from any combination of these letters

So if you receive: abpplead

You should find apples, bad, mats, lead, etc

I know there is no best answer But what reasonable and effective methods, what data structure to use, and so on

In addition, suppose you can preprocess the input, so you can choose to store the input letters in any data structure you want

Solution

Put the dictionary in Terry The letters are then placed in the counter array indexed by their character values, keeping the count of each letter (let this be called []) Then the trie is traversed in the depth first search order. When traversing down, the count [letter] value of each letter is decremented, and it is incremented on the way back Now, any time the count [letter] is about to be negative, stop and move back Each time the word terminator is reached, the result is output