Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

Example 2:

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

1) Explain the problem

The problem is to find the shortest transformation sequence 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 the new word must be in the wordList. The goal is to determine the number of words in this shortest transformation sequence or return 0 if no such sequence exists.

2) Short easy to remember solution/approach

Use Breadth-First Search (BFS) to explore all possible transformations level by level.
Use a queue to manage the BFS traversal, starting from the beginWord.
Use a set for wordList to quickly check if a word is valid and to remove words as they are visited to avoid cycles.

3) Solution in JavaScript with code commenting

function ladderLength(beginWord, endWord, wordList) {
    const wordSet = new Set(wordList);
    if (!wordSet.has(endWord)) return 0;

    const queue = [[beginWord, 1]]; // Queue of [currentWord, currentLevel]

    while (queue.length > 0) {
        const [currentWord, level] = queue.shift();

        // If the current word is the end word, return the current level
        if (currentWord === endWord) return level;

        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)) {
                    queue.push([newWord, level + 1]);
                    wordSet.delete(newWord); // Remove word to prevent re-visiting
                }
            }
        }
    }

    return 0; // No valid transformation found
}

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

Imagine you are playing a word game where you start with a word and can change one letter at a time to form a new word, aiming to reach a specific end word. You have a list of valid words you can use. You want to find the shortest path from the start word to the end word. To do this, you explore all possible single-letter changes at each step, making sure each new word is valid. This is similar to navigating a maze where each step leads to a new word, and you want to find the shortest path to the goal.

5) Code explanation in pointers

Initialize Set: Convert wordList to a set for O(1) lookup and check if endWord is in the set.
BFS Initialization: Start BFS with a queue containing the beginWord and the initial level (1).
BFS Traversal:
- Dequeue: Remove the front element of the queue.
- End Word Check: If the current word matches the endWord, return the current level.
- Word Transformation: Generate all possible single-letter transformations of the current word.
- Validity Check: For each new word, if it's in the set, add it to the queue and remove it from the set to mark as visited.
No Transformation: If the queue is exhausted without finding the endWord, return 0.

6) Complexities

Time Complexity: O(m n 26) where m is the length of each word, n is the number of words in the wordList, and 26 is the number of letters in the alphabet. The worst-case scenario explores all possible single-letter transformations for each word.
Space Complexity: O(m * n) for the queue and set storage, where m is the length of each word and n is the number of words in the wordList.

Word Ladder - BFS