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

Question

Hello, everyone!

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?

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

Thanks for your time!

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

You could also store the strings with characters sorted in ASCIIbetical order into a std::set, then sort the player's letters into the same order and search the map for each substring of the player's letters.

Answer 3

How about keeping the pairs {word from the dictionary, string consisting of the same letters but in ascending order (sorted)}

Then sort the vector of those pairs based on the second string and compare using binary search with a string consisting of sorted letters from players hand.

Answer 4

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.

Answer 5

There have been numerous papers and questions on Scrabble on this site.

There are many strategies available too.

The representation of your dictionary is inadequate, there are much clever methods available. For example, check what a Trie is on wikipedia.

Using this you can implement a backtracking algorithm to quickly determine which words you can form.

{'as', 'ape', 'gum'}

Trie:

void -a-> (n) -p-> (n) -e-> (y)
              -s-> (y)
     -g-> (n) -u-> (n) -m-> (y)

Where 'n' means that it does not form a word and y means that it does.

Now, you just have to walk the Trie, keeping in mind what letters are available.

Say that you have {'a', 'p', 'g', 'm', 'u'}:

 1. I have a 'a' (but 'a' is not a word)
 2. I have a 'p' (but 'ap' is not a word)
 3. I don't have any 'e' so I can't go further, let's backtrack
 4. I don't have any 's' so...
 5. I have a 'g', but it's not a word
 6. I have a 'u', but 'gu' is not a word
 7. I have a 'm' and 'gum' is a word, I store it somewhere, I can't go further

The point is to maintain a set of the available letters, when you take the -a-> branch, you remove 'a' from this set, then when you take -a-> in reverse (while backtracking) you add it back in the set.

• This structure is much more space efficient, it actually models a Finite Automaton which recognize the language of your dictionary instead of blindly saving all words
• The runtime should be much faster as well, since you'll never go deep in the tree-structure (you only have 7 letters available)
• It's certainly not what I'd do, since it does not take the board into account :p

' ' letters mean you can take any of the available branches. You don't need to use a blank if you have the required letter.

Answer 6

There are some good answers here already, and I think a trie is probably the right way to go, but this is an interesting problem so I'll toss in my two cents' worth...

The naive approach would be to generate all permutations of the available letters and of all distinct subsets, then search for each potential word in the dictionary. The problem is that, while it's not hard to do this, there is a surprisingly large number of potential words, and most of them are invalid.

On the positive side, checking the dictionary can be sped up with a binary search or something similar. On the negative side, you'd be doing this so many times that the program would grind to a halt for long lists of letters.

We definitely need to preprocess the dictionary to make it more useful, and what we really need is to have a way to quickly rule out most of the potential matches, even if the method has occasional false positives.

One way to do this would be to represent which letters a word uses in a bit map. In other words, precalculate a 32-bit number for each word in the dictionary, where each bit is set if the corresponding letter of the alphabet is used in the word at least once. This would allow you to find all potential words by doing a linear scan of the dictionary and keeping only the ones that use only letters you have available. I suspect that, with a bit of cleverness and indexing, you can do better than linear.

Of the candidates you find, some will require more instances of a letter than you have available, so these will be false positives. That means you need to do a final check on all of the candidates you generated to eliminate the almost-hits. There are many ways to do this, but one of the simplest is to go through your list of letters and replace the first occurrence of that letter in the potential word with a dash. When you're done, if the potential word has anything but dashes, it's a failure. A more elegant solution, though not necessarily faster, would be to generate an array of letter frequencies and compare them.

Again, I think tries are probably the way to go, but I hope these ideas are useful to you.

edit

Let me toss out an example of how you could do better than a full linear search on the initial search: use the radix. Keep a simple index that lets you look up the first word that starts with a given letter. Then, when doing the search, skip over all words that start with a letter that you don't have. This is not a gigantic speedup, but it's an improvement.