127. Word Ladder

Problem Description

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

• Every adjacent pair of words differs by a single letter
• Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList
• sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

Examples

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.

from collections import deque, defaultdict

def ladderLength(beginWord: str, endWord: str, wordList: List[str]) -> int:
    if endWord not in wordList:
        return 0
    
    # Create word set for quick lookup
    word_set = set(wordList)
    
    # Create a dictionary to store neighbors
    neighbors = defaultdict(list)
    
    # Build the neighbors dictionary
    def build_neighbors():
        for word in [beginWord] + list(word_set):
            for i in range(len(word)):
                pattern = word[:i] + '*' + word[i+1:]
                neighbors[pattern].append(word)
    
    build_neighbors()
    
    # BFS
    queue = deque([(beginWord, 1)])
    visited = {beginWord}
    
    while queue:
        word, length = queue.popleft()
        
        # Try all possible transformations
        for i in range(len(word)):
            pattern = word[:i] + '*' + word[i+1:]
            for neighbor in neighbors[pattern]:
                if neighbor == endWord:
                    return length + 1
                if neighbor not in visited and neighbor in word_set:
                    visited.add(neighbor)
                    queue.append((neighbor, length + 1))
    
    return 0

class Solution {
    public int ladderLength(String beginWord, String endWord, List wordList) {
        Set dict = new HashSet<>(wordList);
        if (!dict.contains(endWord)) {
            return 0;
        }
        
        Queue queue = new LinkedList<>();
        queue.offer(beginWord);
        Set visited = new HashSet<>();
        visited.add(beginWord);
        int level = 1;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String word = queue.poll();
                char[] chars = word.toCharArray();
                
                for (int j = 0; j < chars.length; j++) {
                    char original = chars[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        chars[j] = c;
                        String newWord = new String(chars);
                        
                        if (newWord.equals(endWord)) {
                            return level + 1;
                        }
                        
                        if (dict.contains(newWord) && !visited.contains(newWord)) {
                            queue.offer(newWord);
                            visited.add(newWord);
                        }
                    }
                    chars[j] = original;
                }
            }
            level++;
        }
        
        return 0;
    }
}

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector& wordList) {
        unordered_set dict(wordList.begin(), wordList.end());
        if (!dict.count(endWord)) {
            return 0;
        }
        
        queue q{{beginWord}};
        unordered_set visited{{beginWord}};
        int level = 1;
        
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                string word = q.front();
                q.pop();
                
                for (int j = 0; j < word.length(); j++) {
                    char original = word[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        word[j] = c;
                        
                        if (word == endWord) {
                            return level + 1;
                        }
                        
                        if (dict.count(word) && !visited.count(word)) {
                            q.push(word);
                            visited.insert(word);
                        }
                    }
                    word[j] = original;
                }
            }
            level++;
        }
        
        return 0;
    }
};

/**
 * @param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {number}
 */
var ladderLength = function(beginWord, endWord, wordList) {
    const dict = new Set(wordList);
    if (!dict.has(endWord)) {
        return 0;
    }
    
    const queue = [[beginWord, 1]];
    const visited = new Set([beginWord]);
    
    while (queue.length) {
        const [word, length] = queue.shift();
        
        for (let i = 0; i < word.length; i++) {
            const chars = word.split('');
            for (let c = 97; c <= 122; c++) {  // ASCII 'a' to 'z'
                chars[i] = String.fromCharCode(c);
                const newWord = chars.join('');
                
                if (newWord === endWord) {
                    return length + 1;
                }
                
                if (dict.has(newWord) && !visited.has(newWord)) {
                    queue.push([newWord, length + 1]);
                    visited.add(newWord);
                }
            }
        }
    }
    
    return 0;
};

public class Solution {
    public int LadderLength(string beginWord, string endWord, IList wordList) {
        HashSet dict = new HashSet(wordList);
        if (!dict.Contains(endWord)) {
            return 0;
        }
        
        Queue queue = new Queue();
        queue.Enqueue(beginWord);
        HashSet visited = new HashSet { beginWord };
        int level = 1;
        
        while (queue.Count > 0) {
            int size = queue.Count;
            for (int i = 0; i < size; i++) {
                string word = queue.Dequeue();
                char[] chars = word.ToCharArray();
                
                for (int j = 0; j < chars.Length; j++) {
                    char original = chars[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        chars[j] = c;
                        string newWord = new string(chars);
                        
                        if (newWord == endWord) {
                            return level + 1;
                        }
                        
                        if (dict.Contains(newWord) && !visited.Contains(newWord)) {
                            queue.Enqueue(newWord);
                            visited.Add(newWord);
                        }
                    }
                    chars[j] = original;
                }
            }
            level++;
        }
        
        return 0;
    }
}