Words & Stuff

I was playing a word game (Capitals, an iOS app that’s apparently no longer available), and I got to wondering how one would go about using a computer to find all the words that you can make with a given set of letters.

I wouldn’t use such a program for playing a game. But I was curious about what the algorithm would be.

In case I didn’t describe the goal clearly above, the idea is essentially the same as what a Scrabble app would need to be able to do to come up with words to play: take a set of n letters, and find all the words (in a given dictionary/word list) that are n or fewer letters long and that use only the given letters. If there are two Bs in the set of letters, then the words listed by the algorithm shouldn’t contain more than two Bs. And so on.

I thought briefly about how I would go about writing a program to do this, but I didn’t get very far. My best guesses about how to approach it seemed like they would execute painfully slowly.

So I went and looked around online, and of course Stack Overflow has some answers:

Given a dictionary and a list of letters find all valid words that can be built with the letters.

I’m not sure that I entirely follow the details of all the answers given there, but I’m fairly confident that I could figure them out in detail if I had to.

But one thing that the answers there don’t explicitly say is that the pre-processing of the dictionary only has to be done once, and then you can use the pre-processed dictionary as many times as you want. Which, I’m guessing, explains how internet Scrabble-word-finder sites operate: they’ve already done the pre-processing, so they can use the processed dictionary to quickly find all the anagrams of a given set of letters (and all subsets of that set).