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 by Bruce)

Bruce,

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.

Thanks,

--- SK

Posted by SilverKnight on 2003-09-26 11:43:00