## Problem

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

Only one letter can be changed at a timeEach intermediate word must exist in the dictionary

Notice: All words have the same length.All words contain only lowercase alphabetic characters.

## Example

Given:

start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return

  [
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]

## Code - Java

public class Solution {
/**
* @param start, a string
* @param end,   a string
* @param dict,  a set of string
* @return a list of lists of string
*/
public List<List<String>> findLadders(String start, String end, Set<String> dict) {
Map<String, List<String>> map = new HashMap<>();
createGraph(start, dict, map);

List<List<String>> result = new ArrayList<>();

Map<String, Integer> distance = new HashMap<>();
Set<String> visited = new HashSet<>();
queue.offer(start);
distance.put(start, 0);
while (!queue.isEmpty()) {
String s = queue.poll();
if (s.equals(end)) continue;
for (String t : map.get(s)) {
if (!visited.contains(t)) {
queue.offer(t);
distance.put(t, distance.get(s) + 1);
}
}
}
assemble(result, map, distance, new ArrayList<String>(Arrays.asList(start)), start, end);
return result;

}

private void assemble(List<List<String>> result, Map<String, List<String>> map, Map<String, Integer> distance, List<String> buffer, String s, String end) {
int currDist = distance.get(s);
int targetDist = distance.get(end);
if (currDist == targetDist && s.equals(end)) {
return;
}
for (String t : map.get(s)) {
if (distance.get(t) == currDist + 1) {
List<String> copy = new ArrayList<>(buffer);
assemble(result, map, distance, copy, t, end);
}
}
}

private void createGraph(String s, Set<String> dict, Map<String, List<String>> map) {
if (map.containsKey(s)) return;
List<String> neighbors = new ArrayList<>();
map.put(s, neighbors);
for (String t : dict) {
if (diffByOne(s, t)) {
createGraph(t, dict, map);
}
}
}

private boolean diffByOne(String a, String b) {
int len = a.length();
int cnt = 0;
for (int i = 0; i < len; i++) {
if (a.charAt(i) != b.charAt(i)) {
if (cnt > 0) return false;
cnt++;
}
}
return cnt == 1;
}
}