Shortest distance from one word to another. eg: cat -> cot -> dot -> dog

Lil' preparation before the interview. This is my solution to the problem in title. The code is pretty straight forward. Requesting suggestions for improvement and also verification of complexity, which I guess is O(26n)

```
public class CatToDog {

static Set dictionary;

static {
dictionary = new HashSet();
dictionary.add("camera");
dictionary.add("cat");
dictionary.add("cot");
dictionary.add("cot");
dictionary.add("dome");
dictionary.add("dot");
dictionary.add("dog");

// dictionary = new TreeSet();
// BufferedReader br = null;
// try {
// try {
// br = new BufferedReader(new FileReader("/Users/ameya.patil/Desktop/text.txt"));
// String line;
// while ((line = br.readLine()) != null) {
// dictionary.add(line.split(":")[0]);
// }
//
// } finally {
// br.close();
// }
// } catch (Exception e) {
// throw new RuntimeException("Error while reading dictionary");
// }

}

private CatToDog () { };

public static List listWords(String startWord, String endWord) {
final Queue queue = new LinkedList();
final Map backTrack = new HashMap();
queue.add(startWord);
backTrack.put(startWord, null);

while (!queue.isEmpty()) {
String currentWord = queue.poll();
if (currentWord.equals(endWord)) {
return mapToList(backTrack, endWord);
}
addValidOneChangeWords(currentWord, queue, backTrack);
}
return Collections.EMPTY_LIST;
}

private static void addValidOneChangeWords(String startWord, Queue queue, Map backTrack) {
for (int

I'm not sure about the exact complexity, but it is certainly huge! One-letter edits are fine to spell check one word given a large dictionary, but does not work if you only have a few words and the edit distance can be arbitrarily large. To look for close words in the dictionary, you should use the Levenshtein distance, as mentioned by ratchet freak. (Implementing the Levenshtein distance is a good idea.)

//        dictionary = new TreeSet();
//        ....

Please don't post unused code here unless you want it reviewed too.

private CatToDog () { };

A default constructor is provided by Java already, only use that if you need to put something in there.

public static List listWords(String startWord, String endWord) {
    final Queue queue = new LinkedList();
    final Map backTrack = new HashMap();
    queue.add(startWord);
    backTrack.put(startWord, null);

    while (!queue.isEmpty()) {
        String currentWord = queue.poll();
        if (currentWord.equals(endWord)) {
            return mapToList(backTrack, endWord);
        }
        addValidOneChangeWords(currentWord, queue, backTrack);
    }
    return Collections.EMPTY_LIST;
}

How do you know this is the shortest path? It feels a lot like depth first search, but I think you want to implement Dijkstra's algorithm instead to be able to notice shorter subpaths.

private static void addValidOneChangeWords(String startWord, Queue queue, Map backTrack) {
    for (int i = 0; i < startWord.length(); i++) {
        char[] endWord = startWord.toCharArray();
        for (char ch = 'a'; ch < 'z'; ch++) {
            endWord[i] = ch;
            String word = new String(endWord);
            if (validate(word, backTrack, startWord)) {
                queue.add(word);
                backTrack.put(word, startWord);
            }
        }
    }
}

You're only focusing on one-letter edits here, but what about deletions, insertions and even transpositions (dog -> dgo)? The Damerau-Levenshtein distance handles them.

And finally, mapToList is poorly named: I already know that the type change, I want to know about semantics! Something like editPath would be better.

StackExchange Code Review Q#36463, answer score: 3