## Thursday, July 24, 2014

### 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) {
Set<String> visited = new HashSet<String>();
Map<String, String> routes = new HashMap<String, String>();
while (!Q.isEmpty()) {
String t = Q.poll();
if (t.equals(des)) {
while (t != null) {
t = routes.get(t);
}
return list;
}
for (String o : getAllTransformations(t, dictionary)) {
if (!visited.contains(o)) {
routes.put(o, t);
}
}
}
return null;
}

private static List<String> getAllTransformations(String src,
Set<String> dictionary) {
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))
}
}
return results;
}
```

Thanks.

References