Word Game

Hope everyone is having a fantastic day so far!

Please see the image below to see the type of word game this post is about.

I have a text file of words that gets split and every word is added to an array.
With the 4 letters on the right side (of the image) is it possible to go through an array of words to find out how many words can be created from those 4 letters (BSTU). If this is possible does anyone know how I would go about it (I don't need code just a point in the right direction). THANK YOU!

 

I actually just wrote this exact thing recently for a project I'm working on.

The solution I used is to first build up a prefix tree from your dictionary. So for example if your dictionary is:

"hat"
"hate"
"hello"
"hear"

your prefix tree ends up looking like this:


Each letter is a node which can optionally have a child for each character which represents the next character in the word. The blue checkmarks mean "The tree from the root to here represents a full word".

Once you have this tree, you can use your pool of letters from your starting word (BSTU from your example) to recursively traverse this tree to build up all possible words you can make from those letters.

What I didn't picture in my tree above is that the "root" node of the whole tree should actually be a "blank" character to represent an empty word, so that the word can begin with any character.

 

Whoa!
Thank you so much that’s much more elegant than what I was thinking. It didn’t even dawn on me that the list is in order too

it’s greatly appreciated thank you for taking the time to share. THIS IS AWESOME!

 

No problem. If you run into troubles with the implementation, feel free to post again here and I can try to help.

 

You the man! Again thank you