Word ladder solution in Java using matrix

Question

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that only one letter can be changed at a time and each intermediate word must exist in the dictionary. For example, given:

start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

One shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", the program should return its length 5.

The following is my implementation of Word Ladder problem. Can anybody review the code to compare its efficiency with other solutions?

package arrays;

import java.util.Hashtable;
import java.util.Set;

public class WordLadder {

public static void main(String[] args) throws Exception {
    wordLadder();
}

private static void wordLadder() throws Exception {
    String source = "hit";
    String destination = "cog";
    Hashtable<Integer, String> dict = new Hashtable<Integer, String>();
    dict.put(1, source);
    dict.put(2, "hot");
    dict.put(3, "dot");
    dict.put(4, "dog");
    dict.put(5, "lot");
    dict.put(6, "log");
    dict.put(7, destination);
    formHammingDistanceMat(dict);
}

private static void formHammingDistanceMat(
        Hashtable<Integer, String> dict) throws Exception {
    int mat[][] = new int[dict.size()][dict.size()];
    for (int[] row : mat) {
        java.util.Arrays.fill(row, 99999);
    }

    Set<Integer> keySet = dict.keySet();
    for (int i = 0; i < keySet.size() - 1; i++) {
        String mainString = dict.get(i + 1);
        for (int j = i + 2; j <= dict.size(); j++) {
            if (j == 7)
                System.out.println();
            mat[i][j - 1] = findHamming(mainString, dict.get(j));
        }
    }
    System.out.println(findShortestPath(mat, 0, 1,dict));
}

private static int findShortestPath(int[][] mat, int row, int col,
        Hashtable<Integer, String> dict) {
    if (col == dict.size()-1) {
        return 0;
    }
    if (mat[row + 1][col + 1] == 1) {
        return 1 + findShortestPath(mat, row + 1, col + 1, dict);
    } else if (mat[row][col + 1] == 1) {
        return 1 + findShortestPath(mat, row, col + 1, dict);
    } else
        return 1 + findShortestPath(mat, row + 1, col, dict);
}

private static int findHamming(String mainString, String str)
        throws Exception {
    if(mainString.length()!=str.length()) throw new Exception();
    int count = 0;
    for (int i = 0; i < mainString.length(); i++) {
        if (mainString.charAt(i) != str.charAt(i))
            count++;
    }
    return count;
}
}

Answer 1

package arrays;

Wrong, unless it's your name and you've registered the top-level domain arrays. Seriously, use a personal package prefix, even for toy code.

import java.util.Hashtable;

Hashtable still exists? :D Forget it, and use HashMap (it's about the same, but not synchronized and much more in use).

Hashtable<Integer, String> dict = new Hashtable<Integer, String>();
dict.put(1, source);
dict.put(2, "hot");

That's what arrays are good for, you need no map here.

java.util.Arrays.fill(row, 99999);

Feel free to import it. Is 99999 enough? Sure, but the classical choice is Integer.MAX_VALUE. But this may lead to overflow, so sticking with a smaller constant is fine. Just declare the constant as

private final int VERY_FAR = 99999;

so that your code is not filled with essentially random numbers.

for (int i = 0; i < keySet.size() - 1; i++) {
    String mainString = dict.get(i + 1);
        for (int j = i + 2; j <= dict.size(); j++) {

You shouldn't have started the numbering with 1. Now there's i, i+1, i+2, pretty confusing. Actually, you shouldn't numbered the words at all, simply

List<String> dict = Arrays.asList(
    new String[]{"hot","dot","dog","lot","log"});

would do. Actually, you could stick with an array like

String[] dict = {"hot","dot","dog","lot","log"};

but lists are nearly always preferred.

You're computing the hamming distance of all word pairs. Google says

The number of words in the English language is: 1,025,109.8.

which means some 1e12 pairs. You'd need a pretty smart algorithm to avoid this pairing, so let's forget it for now.

However, the problem is that you compute all the distances, while

• you don't really need them
• they don't really help

You don't need the distance, all you need is to know if two words are neighbors (i.e., a boolean instead of an int). But actually, the question is not "given two words, determine their distance", but "starting with dog, where can I go?". So what you need is something like

Map<String, Set<String>> neighbors;

and then a path-finding algorithm (which actually could make use of knowing the distance, but that's a different story).

if(mainString.length()!=str.length()) throw new Exception();

That's too brutal. Mathematically, returning infinity would be perfect. Returning some big number would be fine. Throwing an IllegalArgumentException or some exception of your would be fine, too.

However, it's good that you think about it. Doing nothing would be too bad (distance("hot", "hotdog") would be zero).