1

I want to create a java program that can find the shortest word ladder between two words. It's been suggested that I use a graph data structure with words as nodes. The idea being that nodes with words that are different by only one character are directly connected.

I'm dealing with a text file of possible words that has over 200,000 different words of various lengths. That seems like it would leave me with a great deal of different data structures unless I found some way to connect them.

That's what I'm asking about. How can I connect these separate graphs into one large graph as I add new words to the graph?

1
HashMap<String, List<String>> 

The data structure isn't that big or complicated but populating it will be a chore. Look up hamming distance algorithms. You're looking for a hamming distance of one. When you find two words with that distance add them to each other's list.

Unless you're changing the rules of word ladders you always have words of the same length. So the first thing I'd do is separate your 20,000 word list into structures for each length.

That covers building your data structure. Navigating it is a different task. Minimizing hamming distance also makes a good rule of thumb for graph traversing algorithms here. Greedy might be worth a try.

A key problem here is that this graph is cyclic. It's all to easy to write code that runs around in circles if you don't remember where you've been.

1

Comparing every word against every other word (even limiting to the same length), is a fairly expensive operation. One way to do this faster is to create a reverse index that replaces every letter with a *. For example (after removing all indices with only one entry):

*est -> [nest, best]
ne*t -> [nest, next]
be*t -> [belt, best]

You can either use this index directly, or take a second pass to generate the neighbors. This makes your index creation O(n) instead of O(n2), where n is the number of words in your dictionary.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.