Random commentary about C++, STL, Boost, Perl, Python, Algorithms, Problem Solving and Web Search
Friday, March 6, 2009
Edit step ladder
Yet another edit step game. This time you have a dictionary of words D. A word wi can mutate into a word wjif a single character is added, deleted, or changed. This operation is called edit step. An edit step ladder is a lexicographically ordered sequence of words w1... wn, such as the transformation from wi to wi+1 is an edit step. Find the longest edit step ladder in D in optimal space and time.