Word Ladder

okay so in yet another random query on Google to unearth some good Stanford stuff that's freely available on their website, I found a very interesting problem called "Word Ladders" here. The problem asks you to try and build a chain of words given a start word and an end word such that every pair of consecutive words in your chain differs only by 1 character. Sure was a good find but i was a little upset that while they teach this stuff to undergrads at Stanford, I had not heard about it until after 2years of completing a Masters program in CS at "not Stanford". Nevertheless i set out to try and solve it on my own in JAVA. The classic problem asks you to build the word ladder from an english lexicon but i scaled it down to an Arraylist of words and a start and end word supplied by the user.

Spent some time trying to implement this "suggested algorithm" but since i had a solution ready in my mind i couldn't get myself to complete that implementation. Here's what i came up with. Uses recursion and backtracking. The intention of sharing this source code is to help the curious and the enthusiastic few who want to solve it but might not quite have an idea on where to start.

Also this is somewhat shabby code so if you are reading this and have already solved this problem or are going to, let me know if you come up with something better. Also if you happen to be in the elite group of coders who refuse to solve seemingly trivial problems i suggest you leave a comment at the very least to help me improve it. And if you were looking for a quick solution to an "commonly asked interview question" or a school homework then the good news is i haven't given you the helper functions.. so you cant copy paste and get it to work. You are atleast 30minutes of coding time away from seeing the output :D

The source code:

public static boolean findLadder(String start, String end, List words, List ladder, int position)

{

//1. To be able to use list.set method when backtracking.

ladder.add("");

if(start.equals(end))

{

for(int i=ladder.size()-1;i>position;i--)

ladder.set(i, "");

return true;

}

//2. Find closest words to the "current" start word. (Write your own)

//@param:start: the start word, words: a list of words that you want to scan through.

List closestWordList = findClosest(start, words);

if(closestWordList.size()==0) return false;

for(String eachClosest:closestWordList)

{

List remainingWords = new ArrayList();

remainingWords.addAll(words);

remainingWords.remove(start);

remainingWords.remove(eachClosest);

if(findLadder(eachClosest,end,remainingWords,ladder, position+1))

{

ladder.set(position+1, eachClosest);

ladder.set(0, start); //to set the start word in the final output.

if(position+1==1)

printLadder(ladder);

}

else

{

for(int i=position;i

ladder.set(i, "");

}

}

ladder.set(0, start);

return true;

}

So why did i get back to blogger after a year.. well just happened to read Steve Yegge's blogs and thought of giving my 2cents to the world. I am going to post a few more dry blogs with solutions to a few good problems and hope my fellow developers join the fun.