Word Ladder in Java

As always, we can find best definitions and back ground of anything in wiki. Here is the link for details http://en.wikipedia.org/wiki/Word_ladder.

Here, I just want to give an idea of how can we solve a word ladder puzzle in java. The goal is to find a "path" from a given source word to a destination word, the nodes in the path should only differ by one letter.

From the statement it is clear that its a basic "Graph" problem, and to find the shortest path "Breadth First Search" is the best suited approach.

Here, I have mentioned a basic approach, which works fine, I have written another approach to explain how Graphs work in real world (the basic idea is similar to this). You can find that in my Git repo https://github.com/rajendrag/word-ladder.

Here, we try to replace each character in source string with all possible characters (a to z) and check if the word is exists in the dictionary, if it is there, we add that new word to the 'queue' to process further (like adding vertex in a graph). While we doing this we remove the newly found word from dictionary to avoid recurrences and infinity loop.

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class WordLadder2 {

    /**
     * @param args
     */
    public static void main(String[] args) {
        WordLadder2 ladder = new WordLadder2();
        List<String> dictionary = ladder.readWords();
        Word wordLadder = ladder.findLadder("fool", "sage", dictionary);
        ladder.printLadder(wordLadder);
        Word wordLadder1 = ladder.findLadder("cold", "warm", dictionary);
        ladder.printLadder(wordLadder1);
    }

    private void printLadder(Word wordLadder) {
        if(wordLadder == null) {
            System.out.println();
            return;
        }
        printLadder(wordLadder.parent);
        System.out.print(wordLadder.word+" -> ");
        
    }

    private Word findLadder(String source, String dest, List<String> dictionary) {
        if (null == source || null == dest || source.trim().length() == 0 || dest.trim().length() == 0 || null == dictionary || dictionary.size() == 0) {
            return null;
        }
        if (source.length() != dest.length()) {
            return null;
        }

        Queue<Word> queue = new LinkedList<Word>();
        Word start = new Word(source);
        queue.add(start);
        while (!queue.isEmpty()) {
            Word current = queue.poll();
            
            char[] sChars = current.word.toCharArray();
            for (int j=0; j<sChars.length; j++){
                char original=sChars[j];
                  for (char c='a'; c<='z'; c++){
                      if (c==sChars[j]){
                          continue;
                      }
                      sChars[j]=c;
                      String tempStr=String.copyValueOf(sChars);
                      Word newWord = new Word(tempStr);
                      newWord.parent = current;
                      if (tempStr.equals(dest)){
                          return newWord;
                      }
                      
                     if (dictionary.contains(tempStr)){
                         queue.add(newWord);
                         dictionary.remove(tempStr);
                     }
                }
                sChars[j]=original;
          }
        }
        return null;
    }

    private List<String> readWords() {
        List<String> words = new ArrayList<String>();
        try {
            BufferedReader br = new BufferedReader(new FileReader(new File("wordfile.txt")));
            String word = null;
            while ((word = br.readLine()) != null) {
                words.add(word.toLowerCase());
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
        return words;
    }

    class Word {
        String word;
        Word   parent;// the parent, is only is to find the path recursively

        public Word(String word) {
            this.word = word;
        }

    }
}

Here is a sample "wordfile.txt", place this file in projects home directory.

FOOL
CORD
FOUL
FOIL
FAIL
FALL
CARD
PALL
POLE
POOL
POLL
WARM
COOL
PALE
PAGE
POPE
SALE
SAGE
COLD
WARD