Word Ladder hard

Problem Statement

Given two words, beginWord and endWord, and a dictionary's word list wordList, return the shortest transformation sequence from beginWord to endWord, such that:

  1. Only one letter can be changed at a time.
  2. Each intermediate word must exist in the wordList.

If there is no such transformation sequence, return an empty array.

Example 1

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

Output: ["hit","hot","dot","dog","cog"]

Explanation: "hit" -> "hot" -> "dot" -> "dog" -> "cog" is the shortest transformation sequence.

Example 2

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

Output: []

Explanation: The endWord "cog" is not in wordList, therefore no valid transformation sequence exists.

Steps

  1. Initialization: Add beginWord to a queue queue and a set visited. Initialize a variable result to store the transformation sequence (initially an array containing beginWord).

  2. Breadth-First Search (BFS): While the queue is not empty:

    • Dequeue the current word currentWord.
    • If currentWord is equal to endWord, the transformation sequence is found. Return result.
    • Generate all possible one-letter different words from currentWord.
    • For each generated word:
      • If the word is in wordList and not in visited:
        • Enqueue the word.
        • Add the word to visited.
        • Add the word to a new array newResult which will store the updated transformation sequence.

  3. Update Result: After processing all neighbors of currentWord, update result with newResult.

  4. No Transformation Sequence: If the loop completes without finding endWord, return an empty array.

Explanation

The algorithm uses Breadth-First Search (BFS) to find the shortest path. BFS guarantees that the first time we encounter the endWord, we've found the shortest path because it explores all words at a given distance from the beginWord before moving to words further away. The visited set prevents cycles and redundant explorations.

Code

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

    const queue: [string, string[]] = [[beginWord, [beginWord]]];
    const visited = new Set<string>();
    visited.add(beginWord);
    let result: string[][] = [];

    while (queue.length > 0) {
        const [currentWord, path] = queue.shift()!;
        if (currentWord === endWord) {
            result.push(path);
            continue; //Found a path, but continue to search for shorter ones.
        }
      
        for (let i = 0; i < currentWord.length; i++) {
            for (let j = 0; j < 26; j++) {
                const charCode = 'a'.charCodeAt(0) + j;
                const newWord = currentWord.substring(0, i) + String.fromCharCode(charCode) + currentWord.substring(i + 1);
                if (wordSet.has(newWord) && !visited.has(newWord)) {
                    queue.push([newWord, [...path, newWord]]);
                    visited.add(newWord);
                }
            }
        }
    }

    //Return only the shortest paths
    if (result.length > 0) {
        let shortestLength = result[0].length;
        return result.filter(path => path.length === shortestLength);
    }
    return [];
}

Complexity

  • Time Complexity: O(M * N * 26), where M is the length of words and N is the number of words in the word list. We iterate through each word and each position in the word to explore possible transformations.
  • Space Complexity: O(M * N) in the worst case, due to the visited set and the queue which could potentially store all words in the word list. In practice, it will often be less than this.