Word Ladder

127.Word Ladder

Breadth-First Search

String

Hash Table

Problem Statement:

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that: 1. Only one letter can be changed at a time. 2. Each transformed word must exist in the word list.

Example:

Input:

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

→

Output:

5

Shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", length 5

Algorithm:

1. Convert word list to HashSet for O(1) lookup
2. Use BFS to find shortest path
3. Generate all possible one-letter transformations
4. Track visited words by removing from set

Complexity:

Time: O(N * 26 * L) | Space: O(N) where N is dictionary size, L is word length

Java Solution:

public int ladderLength(String beginWord, String endWord, List wordList) {
    // Convert to HashSet for O(1) lookups
    Set dict = new HashSet<>(wordList);
    
    // Check if endWord exists in dictionary
    if (!dict.contains(endWord)) {
        return 0;
    }
    
    // Initialize queue for BFS
    Queue queue = new LinkedList<>();
    queue.add(beginWord);
    int dist = 1;
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        
        // Process all words at current level
        for (int i = 0; i < size; i++) {
            String currWord = queue.poll();
            if (currWord.equals(endWord)) 
                return dist;
            
            // Try changing each character
            for (int j = 0; j < currWord.length(); j++) {
                char[] chars = currWord.toCharArray();
                
                // Try all possible characters
                for (char c = 'a'; c <= 'z'; c++) {
                    chars[j] = c;
                    String nextWord = new String(chars);
                    
                    // If word exists in dictionary
                    if (dict.contains(nextWord)) {
                        dict.remove(nextWord);  // Mark as visited
                        queue.add(nextWord);
                    }
                }
            }
        }
        dist++;  // Move to next level
    }
    
    return 0;
}

Python Solution:

def ladderLength(self, beginWord: str, endWord: str, 
                wordList: List[str]) -> int:
    # Convert to set for O(1) lookups
    word_set = set(wordList)
    
    if endWord not in word_set:
        return 0
        
    queue = deque([beginWord])
    dist = 1
    
    while queue:
        # Process current level
        for _ in range(len(queue)):
            curr_word = queue.popleft()
            if curr_word == endWord:
                return dist
            
            # Try all transformations
            for i in range(len(curr_word)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    next_word = curr_word[:i] + c + curr_word[i+1:]
                    if next_word in word_set:
                        word_set.remove(next_word)
                        queue.append(next_word)
        dist += 1
        
    return 0

C++ Solution:

int ladderLength(string beginWord, string endWord, 
                  vector& wordList) {
    unordered_set dict(wordList.begin(), wordList.end());
    
    if (!dict.count(endWord)) 
        return 0;
    
    queue q{{beginWord}};
    int dist = 1;
    
    while (!q.empty()) {
        int size = q.size();
        
        for (int i = 0; i < size; i++) {
            string curr = q.front();
            q.pop();
            
            if (curr == endWord) 
                return dist;
            
            // Try all transformations
            for (int j = 0; j < curr.length(); j++) {
                char orig = curr[j];
                for (char c = 'a'; c <= 'z'; c++) {
                    curr[j] = c;
                    if (dict.count(curr)) {
                        dict.erase(curr);
                        q.push(curr);
                    }
                }
                curr[j] = orig;
            }
        }
        dist++;
    }
    
    return 0;
}