Course4all
Join us on telegram
Home/dsa/Trie/Word Ladder II

Word Ladder II

Master this topic with zero to advance depth.

Word Ladder II

Given two words, beginWord and endWord, and a dictionary wordList, return all shortest transformation sequences from beginWord to endWord. Only one letter can be changed at a time.

Hard

Examples

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

Level I: Standard BFS (Shortest Transformation)

Intuition

Use a standard BFS to find the shortest distance from beginWord to endWord. In each step, change one character at a time and check if it exists in the dictionary. This approach only finds the length of the shortest path, not the actual paths themselves.

⏱ O(N * L * 26)💾 O(N * L)
java
class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        Set<String> dict = new HashSet<>(wordList);
        if (!dict.contains(endWord)) return new ArrayList<>();
        Queue<List<String>> q = new LinkedList<>();
        q.add(Arrays.asList(beginWord));
        List<List<String>> res = new ArrayList<>();
        Set<String> visited = new HashSet<>(); visited.add(beginWord);
        boolean found = false;
        while (!q.isEmpty() && !found) {
            int size = q.size();
            Set<String> localVisited = new HashSet<>();
            for (int i = 0; i < size; i++) {
                List<String> path = q.poll();
                String last = path.get(path.size() - 1);
                for (String next : neighbors(last, dict)) {
                    if (next.equals(endWord)) {
                        found = true; List<String> newPath = new ArrayList<>(path);
                        newPath.add(next); res.add(newPath);
                    } else if (!visited.contains(next)) {
                        localVisited.add(next); List<String> newPath = new ArrayList<>(path);
                        newPath.add(next); q.add(newPath);
                    }
                }
            }
            visited.addAll(localVisited);
        }
        return res;
    }
    private List<String> neighbors(String s, Set<String> dict) {
        List<String> res = new ArrayList<>();
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char old = chars[i];
            for (char c = 'a'; c <= 'z'; c++) {
                chars[i] = c; String next = new String(chars);
                if (dict.contains(next)) res.add(next);
            }
            chars[i] = old;
        }
        return res;
    }
}
Approach 2

Level III: BFS + Backtracking (Trie for Neighbors)

Intuition

Use BFS to find the shortest distance from beginWord to all reachable words. To quickly find 'neighbors' (words differing by one char), we can iterate through each position of the word and try all 26 letters, checking against a Set/Trie. Finally, use DFS to backtrack all shortest paths from beginWord to endWord using the distance levels found in BFS.

⏱ O(N * L * 26 + Paths).💾 O(N * L).
java
import java.util.*;
class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        Set<String> set = new HashSet<>(wordList);
        if (!set.contains(endWord)) return new ArrayList<>();
        Map<String, Integer> dist = new HashMap<>();
        dist.put(beginWord, 0);
        Queue<String> q = new LinkedList<>(); q.add(beginWord);
        while(!q.isEmpty()){
            String curr = q.poll();
            if(curr.equals(endWord)) break;
            for(int i=0; i<curr.length(); i++){
                char[] chars = curr.toCharArray();
                for(char c='a'; c<='z'; c++){
                    chars[i] = c; String next = new String(chars);
                    if(set.contains(next) && !dist.containsKey(next)){
                        dist.put(next, dist.get(curr) + 1); q.add(next);
                    }
                }
            }
        }
        List<List<String>> res = new ArrayList<>();
        if(!dist.containsKey(endWord)) return res;
        dfs(endWord, beginWord, dist, new LinkedList<>(Arrays.asList(endWord)), res);
        return res;
    }
    private void dfs(String curr, String target, Map<String, Integer> dist, LinkedList<String> path, List<List<String>> res) {
        if (curr.equals(target)) { List<String> copy = new ArrayList<>(path); Collections.reverse(copy); res.add(copy); return; }
        for (int i=0; i<curr.length(); i++) {
            char[] chars = curr.toCharArray();
            for (char c='a'; c<='z'; c++) {
                chars[i] = c; String next = new String(chars);
                if (dist.containsKey(next) && dist.get(next) == dist.get(curr) - 1) {
                    path.add(next); dfs(next, target, dist, path, res); path.removeLast();
                }
            }
        }
    }
}
← Previous QuestionPrefix and Suffix Search
Next Question →Concatenated Words