Word Ladder II

Share

Find all shortest transformation sequences from beginWord to endWord, one letter at a time.

Example 1
Input: beginWord="hit", endWord="cog", wordList=["hot","dot","dog","lot","log","cog"] → Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
Example 2
Input: beginWord="hit", endWord="cog", wordList=["hot","dot","dog","lot","log"] → Output: []

Solution Approach

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
Java
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)