Finding what words a set of letters can create?

Question

I am trying to write some SQL that will accept a set of letters and return all of the possible words it can make. My first thought was to create a basic three table database like so:

Words -- contains 200k words in real life
------
1 | act
2 | cat

Letters -- contains the whole alphabet in real life
--------
1  | a
3  | c
20 | t

WordLetters --First column is the WordId and the second column is the LetterId
------------
1  | 1
1  | 3
1  | 20
2  | 3
2  | 1
2  | 20

But I'm a bit stuck on how I would write a query that returns words that have an entry in WordLetters for every letter passed in. It also needs to account for words that have two of the same letter. I started with this query, but it obviously does not work:

SELECT DISTINCT w.Word 
FROM Words w
INNER JOIN WordLetters wl
ON wl.LetterId = 20 AND wl.LetterId = 3 AND wl.LetterId = 1

How would I write a query to return only words that contain all of the letters passed in and accounting for duplicate letters?

---

Other info:

My Word table contains close to 200,000 words which is why I am trying to do this on the database side rather than in code. I am using the enable1 word list if anyone cares.

Answer 1

Ignoring, for the moment, the SQL part of the problem, the algorithm I'd use is fairly simple: start by taking each word in your dictionary, and producing a version of it with the letters in sorted order, along with a pointer back to the original version of that word.

This would give a table with entries like:

sorted_text word_id
act         123    /* we'll assume `act` was word number 123 in the original list */
act         321    /* we'll assume 'cat' was word number 321 in the original list */

Then when we receive an input (say, "tac") we sort it's letters, look it up in our table of sorted letters joined to the table of the original words, and that gives us a list of the words that can be created from that input.

If I were doing this, I'd have the tables for that in a SQL database, but probably use something else to pre-process the word list into the sorted form. Likewise, I'd probably leave sorting the letters of the user's input to whatever I was using to create the front-end, so SQL would be left to do what it's good at: relational database management.