Write an algorithm to solve word ladders such as Word Meld 1
or Word Meld 2
. Input consists of the
starting and ending words and the maximum number of steps allowed. Available are files containing lists of
words of any given length; call one such file, say WORDS5.TXT containing a list of words of 5 letters each, and so on.
(In reply to Finding adjacent words
This is a useful footnote, and makes much sense, provided we have a sorted list of adjacent words. (You loosely answered my earlier question regarding what one might do in preprocessing, and I take for granted that we would have sorted all this ahead of time.)
As for the "double-headed" algorithm you describe, I'm not certain that I understand what you're suggesting. Namely, it doesn't seem to reduce the BIG-O speed, and now you not only have to search for adjacent words in two trees... you must do a search (log n, I'm sure) in the other tree to see if it exists there.
So... I see the benefit of doing more in memory, reducing disk access in a practical sense, but I don't see how this speeds the algorithm up (from an algorithmic point of view).
Perhaps you can clarify for me.