C++ - How to efficiently find out if any string in a vector can be assembled from a set of letters

Question

I am implementing a text-based version of Scrabble for a college project.

I have a vector containing around 400K strings (my dictionary), and, at some point in every turn, I'm going to have to check if there's still a word in the dictionary which can be formed with the pieces in the player's hand. I'm checking if the player has any move left... If not, it's game over for the player in question...

My only solution to this is iterating through the string, one by one, and using a sub-routine I have to check if the string in question can be formed from the player's pieces. I'll implement a quickfail checking if the user has any vowels, but it'll still be woefully inefficient.

The text-file containing the dictionary is already alphabetically ordered, so the vector is sorted.

Any suggestions?

---

A problem was presented in the comments below: Any suggestion on how do I take the letters already on the board into account?

Answer 1

Without giving you any specific code (since this is homework after all), one general approach to consider is to map from the sorted letters in the word to the actual legal words.

That is to say, if your dictionary file had only the words ape, gum, and mug, your data structure would look like:

aep -> ape
gmu -> gum, mug

Then you can simply go through permutations of the player's letters, and quickly identify if that key exists in the map.

You pay a little bit of processing time setting up the dictionary at startup, but then you only have to perform a few quick lookups rather than iterating through the whole list every time.

Answer 2

Sounds like a variation of the subset sum problem: http://en.wikipedia.org/wiki/Subset_sum_problem

Maybe some of the described algorithms would help you.