Transform one word into another by changing only one letter at a time

Problem

Given two words of equal length that are in a dictionary, write a method to transform one word into another word by changing only one letter at a time. The new word you get in each step must be in the dictionary.
EXAMPLE
Input: DAMP, LIKE
Output: DAMP -> LAMP -> LIMP -> LIME -> LIKE

Solution

Try thinking this problem in terms of graphs: Consider all words in a dictionary as vertices, and insert an edge between each two vertices that differ by only one letter. The output is a well-known object in the graph, and you probably already know an algorithm to solve the problem.

The output is a path in the graph, and the question is solved by finding a path. A breadth-first search (BFS) or Dijkstra's algorithm solve the problem elegantly.


Java code

public static List<String> transform(String src, String des,
    Set<String> dictionary) {
    Queue<String> Q = new LinkedList<String>();
    Set<String> visited = new HashSet<String>();
    Map<String, String> routes = new HashMap<String, String>();
    Q.add(src);
    visited.add(src);
    while (!Q.isEmpty()) {
        String t = Q.poll();
        if (t.equals(des)) {
            LinkedList<String> list = new LinkedList<String>();
            while (t != null) {
                list.add(0, t);
                t = routes.get(t);
            }
            return list;
        }
        for (String o : getAllTransformations(t, dictionary)) {
            if (!visited.contains(o)) {
                visited.add(o);
                Q.add(o);
                routes.put(o, t);
            }
        }
    }
    return null;
}
 
private static List<String> getAllTransformations(String src,
        Set<String> dictionary) {
    List<String> results = new LinkedList<String>();
    for (int i = 0; i < src.length(); ++i) {
        for (char c = 'A'; c <= 'Z'; ++c) {
            String newStr = src.substring(0, i) + c + src.substring(i + 1);
            if (!src.equals(newStr) && dictionary.contains(newStr))
                results.add(newStr);
        }
    }
    return results;
}

Thanks.

References

• http://tianrunhe.wordpress.com/2012/06/10/transform-one-word-into-another-by-changing-only-one-letter-at-a-time/
• http://stackoverflow.com/questions/11509636/transforming-one-word-into-another-word-by-changing-only-one-letter-at-a-time