Find all shortest transformation sequences from beginWord to endWord, one letter at a time.
Input: beginWord="hit", endWord="cog", wordList=["hot","dot","dog","lot","log","cog"] → Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
Input: beginWord="hit", endWord="cog", wordList=["hot","dot","dog","lot","log"] → Output: []
BFS to find shortest path length, then DFS/backtracking to collect all shortest paths.
- BFS to find shortest distance from each word
- Build parent map: word -> set of words that lead to it in shortest path
- DFS from endWord back to beginWord using parent map
- Reverse path and add to result
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
Set<String> wordSet = new HashSet<>(wordList);
Map<String, Integer> dist = new HashMap<>();
dist.put(beginWord, 0);
Queue<String> q = new LinkedList<>();
q.add(beginWord);
Map<String, List<String>> parents = new HashMap<>();
while (!q.isEmpty()) {
String word = q.poll();
int d = dist.get(word);
char[] arr = word.toCharArray();
for (int i = 0; i < arr.length; i++) {
char orig = arr[i];
for (char c = 'a'; c <= 'z'; c++) {
arr[i] = c;
String next = new String(arr);
if (wordSet.contains(next)) {
if (!dist.containsKey(next)) { dist.put(next, d+1); q.add(next); }
if (dist.get(next) == d+1) parents.computeIfAbsent(next, k->new ArrayList<>()).add(word);
}
}
arr[i] = orig;
}
}
List<List<String>> res = new ArrayList<>();
if (!dist.containsKey(endWord)) return res;
LinkedList<String> path = new LinkedList<>();
path.addFirst(endWord);
dfs(endWord, beginWord, parents, path, res);
return res;
}
private void dfs(String word, String begin, Map<String,List<String>> parents, LinkedList<String> path, List<List<String>> res) {
if (word.equals(begin)) { res.add(new ArrayList<>(path)); return; }
for (String parent : parents.getOrDefault(word, Collections.emptyList())) {
path.addFirst(parent);
dfs(parent, begin, parents, path, res);
path.removeFirst();
}
}
- Time Complexity: O(n * m^2)
- Space Complexity: O(n * m)