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

Problem

Solution

See also