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

Question

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(26ⁿ)

public class CatToDog {

        static Set<String> dictionary;

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

    //        dictionary = new TreeSet<String>();
    //        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<String> listWords(String startWord, String endWord) {
            final Queue<String> queue = new LinkedList<String>();
            final Map<String, String> backTrack = new HashMap<String, String>();
            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<String> queue, Map<String, String> 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);
                    }
                }
            }
        }

        private static boolean validate(String word, Map<String, String> backTrack, String startWord) {
            return dictionary.contains(word) && !backTrack.containsKey(word) && !word.equals(startWord);
        }

        private static List<String> mapToList (Map<String, String> backTrack, String endWord) {
            final List<String> wordList = new ArrayList<String>();
            String word = endWord;
            while (backTrack.containsKey(word)) {
                wordList.add(word);
                word = backTrack.get(word);
            }
            Collections.reverse(wordList);
            return wordList;
        }

        public static void main(String[] args) {
           for (String string :  listWords("cat", "dog")) {
               System.out.println(string);
           }
        }
    }

Answer 1

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<String>();
//        ....

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<String> listWords(String startWord, String endWord) {
    final Queue<String> queue = new LinkedList<String>();
    final Map<String, String> backTrack = new HashMap<String, String>();
    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<String> queue, Map<String, String> 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.