Word Ladder II - BFS

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s<sub>1</sub> -> s<sub>2</sub> -> ... -> s<sub>k</sub> such that:

• Every adjacent pair of words differs by a single letter.

• Every s<sub>i</sub> for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.

• s<sub>k</sub> == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return all the shortest transformation sequences from beginWord to endWord, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words [beginWord, s<sub>1</sub>, s<sub>2</sub>, ..., s<sub>k</sub>].

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"]]
Explanation: There are 2 shortest transformation sequences:
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"

Example 2:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: []
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.

---

1) Explain the problem

The problem is to find all shortest transformation sequences from a start word (beginWord) to an end word (endWord) using a given dictionary of words (wordList). Each step in the transformation must change exactly one letter, and each intermediate word must be in the wordList. The task is to return all shortest transformation sequences as lists of words, or an empty list if no such sequence exists.

2) Short easy to remember solution/approach

• Use Breadth-First Search (BFS) to find the shortest path levels from beginWord to endWord.

• Use Depth-First Search (DFS) to backtrack from endWord to beginWord, collecting all valid transformation paths.

3) Solution in JavaScript with code commenting

function findLadders(beginWord, endWord, wordList) {
    const wordSet = new Set(wordList);
    if (!wordSet.has(endWord)) return [];

    const neighbors = {}; // To store the graph
    const distance = {};  // To store distance from beginWord to each word

    const bfs = () => {
        const queue = [beginWord];
        distance[beginWord] = 0;

        while (queue.length > 0) {
            const currentWord = queue.shift();
            const currentDistance = distance[currentWord];
            for (let i = 0; i < currentWord.length; i++) {
                for (let c = 97; c <= 122; c++) { // ASCII codes for 'a' to 'z'
                    const newWord = currentWord.slice(0, i) + String.fromCharCode(c) + currentWord.slice(i + 1);
                    if (wordSet.has(newWord)) {
                        if (!(newWord in neighbors)) neighbors[newWord] = [];
                        neighbors[newWord].push(currentWord);

                        if (!(newWord in distance)) {
                            distance[newWord] = currentDistance + 1;
                            queue.push(newWord);
                        }
                    }
                }
            }
        }
    };

    const dfs = (word, path) => {
        if (word === beginWord) {
            result.push([beginWord, ...path.reverse()]);
            return;
        }
        for (const neighbor of (neighbors[word] || [])) {
            if (distance[neighbor] + 1 === distance[word]) {
                dfs(neighbor, [...path, word]);
            }
        }
    };

    const result = [];
    bfs();
    if (!(endWord in distance)) return [];
    dfs(endWord, []);

    return result;
}

4) Explanation of the solution in an easy-to-understand way with a real-life example

Imagine you are at a start point and need to reach an end point by changing one step at a time, with each step forming a new valid point from a given list. You first find the shortest paths to reach the end point, then backtrack from the end point to the start, collecting all paths that led to the shortest journey. Think of it like finding all possible shortest routes on a map from one city to another.

5) Code explanation in pointers

• Initialize Set: Convert wordList to a set for O(1) lookup.

• Graph and Distance Storage:

  • Neighbors: Store the graph of transformations.

  • Distance: Store the distance from beginWord to each word.

• BFS Function:

  • Queue Initialization: Start BFS with beginWord.

  • Graph Building: For each word, generate all possible one-letter transformations and update neighbors and distances.

• DFS Function:

  • Backtrack Paths: From endWord, backtrack to beginWord using valid transformations that respect the distance property.

• Result Compilation: Collect all valid paths in result.

• Return: Return all collected paths.

6) Complexities

• Time Complexity: O(m n 26 + m * n) where m is the length of each word and n is the number of words in wordList. The BFS explores all transformations and the DFS collects paths.

• Space Complexity: O(m * n) for the graph, distance storage, and paths collection.