Word ladder efficency problem

Question

I have a problem dealing with word ladders. The problem is: given two words and a dictionary file, find the shortest word ladder between the two words. So if given the words cat and pot:

cat -> cot -> pot

That is just an easy example. You get the idea.

The problem is the time constraint, The problem calls for using a graph, which will be really good to use one since the second part of the problem deals with finding the ladder with the least weight.

If I pre-generate the graph (generate the full graph at the program execution) it would take a long long time. Since the algorithm I came up with compared each word to all the other words in the dictionary to find the adjacent nodes. That comes up to O(n^2) comparisons, plus comparing letters of same size words. Which ends up being a lot.

I did a test run with a 1k 3 letter word list and it took 2.6s to generate the graph. That means that with a 200k list it would take 26 hours to generate the graph.

After finding this out I thought about generating a graph starting only from the starting word and then finding all the adjacent nodes(words that are only a letter different) and then all the adjacent nodes for the previous adjacent nodes until the end word is found, or if its not found then there would be no path.

The programming language is C++. Is there a more efficient algorithm I could use for this?

Answer 1

This is an example where the forward links in the graph are difficult to calculate, but the reverse links are quite easy, so index those instead. Go through the word list and create entries for every link back to the word. For example, the word "cat" would generate the following index entries:

".at" -> Set("cat")
"c.t" -> Set("cat")
"ca." -> Set("cat")

Then after indexing "cot", you would have:

".at" -> Set("cat")
"c.t" -> Set("cat", "cot")
"ca." -> Set("cat")
".ot" -> Set("cot")
"co." -> Set("cot")

When this first pass of indexing, which can be done in O(n), is complete, you can do a second O(n) pass to get the forward links. That's just the union of all the sets on the right for a word, minus your original word. Depending on how often you use this mapping, it might be advantageous to not do this full pass, but just calculate it as needed from the first pass.