114. Word Ladder II

Do BFS one layer at a time, but instead of a single parent per word, remember every path that reaches a word at the current shortest distance. Expand the whole current layer simultaneously; stop the moment endWord appears so only shortest sequences are kept.

Why plain BFS isn't enough

Ordinary BFS finds a shortest path; here we need all of them. Keep, for each word reached at the current frontier, the list of shortest paths that arrive there.

Layer-by-layer expansion

layer = { beginWord: [[beginWord]] }        # word -> list of paths
while layer:
    next_layer = {}
    remove all layer words from the dictionary   # prevents revisiting
    for word, paths in layer:
        for each one-letter neighbour nw still in the dictionary:
            for path in paths: next_layer[nw].append(path + [nw])
    if endWord was produced: collect its paths and stop
    layer = next_layer

Removing the whole current layer from the dictionary before building the next one ensures we only ever move forward (no word is used at two different distances), which keeps every collected sequence shortest.

Worked example

beginWord = "hit", endWord = "cog", dict [hot,dot,dog,lot,log,cog].

Two shortest ladders of length 5 exist:

• hit -> hot -> dot -> dog -> cog
• hit -> hot -> lot -> log -> cog

So the answer is [[hit,hot,dot,dog,cog], [hit,hot,lot,log,cog]].

Complexity

• Time: O(N · L^2 · 26) in the worst case (N words, length L), plus path assembly.
• Space: O(N · L) for the frontier and paths.

class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, String[] wordList) {
        Set<String> words = new HashSet<>(Arrays.asList(wordList));
        List<List<String>> res = new ArrayList<>();
        if (!words.contains(endWord)) return res;

        Map<String, List<List<String>>> layer = new HashMap<>();
        List<String> start = new ArrayList<>();
        start.add(beginWord);
        layer.put(beginWord, new ArrayList<>(List.of(start)));

        while (!layer.isEmpty()) {
            Map<String, List<List<String>>> next = new HashMap<>();
            words.removeAll(layer.keySet());
            for (Map.Entry<String, List<List<String>>> e : layer.entrySet()) {
                String w = e.getKey();
                if (w.equals(endWord)) {
                    res.addAll(e.getValue());
                } else {
                    char[] arr = w.toCharArray();
                    for (int i = 0; i < arr.length; i++) {
                        char old = arr[i];
                        for (char c = 'a'; c <= 'z'; c++) {
                            arr[i] = c;
                            String nw = new String(arr);
                            if (words.contains(nw)) {
                                for (List<String> seq : e.getValue()) {
                                    List<String> np = new ArrayList<>(seq);
                                    np.add(nw);
                                    next.computeIfAbsent(nw, z -> new ArrayList<>()).add(np);
                                }
                            }
                        }
                        arr[i] = old;
                    }
                }
            }
            if (!res.isEmpty()) break;
            layer = next;
        }
        return res;
    }
}