LeetCode Hard – Word Ladder

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.

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.

Constraints:

• 1 <= beginWord.length <= 10
• endWord.length == beginWord.length
• 1 <= wordList.length <= 5000
• wordList[i].length == beginWord.length
• beginWord, endWord, and wordList[i] consist of lowercase English letters.
• beginWord != endWord
• All the words in wordList are unique.

Java Solution

To solve this problem, you can use BFS to find the shortest transformation sequence from beginWord to endWord. You can maintain a queue and traverse the possible transformations, marking visited words to avoid revisiting them.

Here’s the Java solution:

import java.util.*;

public class WordLadderLength {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(endWord)) {
            return 0;  // If endWord is not in wordList, return 0
        }

        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.offer(beginWord);
        visited.add(beginWord);

        int transformations = 1;

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                String currentWord = queue.poll();

                // Generate all possible next words by changing one letter at a time
                for (int j = 0; j < currentWord.length(); j++) {
                    char[] charArray = currentWord.toCharArray();
                    for (char c = 'a'; c <= 'z'; c++) {
                        charArray[j] = c;
                        String nextWord = new String(charArray);

                        if (nextWord.equals(endWord)) {
                            return transformations + 1;  // Found the endWord
                        }

                        if (wordSet.contains(nextWord) && !visited.contains(nextWord)) {
                            visited.add(nextWord);
                            queue.offer(nextWord);
                        }
                    }
                }
            }

            transformations++;
        }

        return 0;  // No transformation sequence found
    }

    public static void main(String[] args) {
        WordLadderLength solution = new WordLadderLength();

        // Example 1
        String beginWord1 = "hit";
        String endWord1 = "cog";
        List<String> wordList1 = Arrays.asList("hot", "dot", "dog", "lot", "log", "cog");
        System.out.println(solution.ladderLength(beginWord1, endWord1, wordList1));  // Output: 5

        // Example 2
        String beginWord2 = "hit";
        String endWord2 = "cog";
        List<String> wordList2 = Arrays.asList("hot", "dot", "dog", "lot", "log");
        System.out.println(solution.ladderLength(beginWord2, endWord2, wordList2));  // Output: 0
    }
}

This Java code defines a WordLadderLength class with the ladderLength method, which uses BFS to find the length of the shortest transformation sequence. The provided test cases demonstrate its usage.

Python Solution

Here’s the equivalent Python solution for finding the length of the shortest transformation sequence from beginWord to endWord:

from collections import deque

class WordLadderLength:
    def ladderLength(self, beginWord, endWord, wordList):
        wordSet = set(wordList)
        if endWord not in wordSet:
            return 0  # If endWord is not in wordList, return 0

        queue = deque()
        visited = set()
        queue.append(beginWord)
        visited.add(beginWord)

        transformations = 1

        while queue:
            size = len(queue)

            for _ in range(size):
                currentWord = queue.popleft()

                # Generate all possible next words by changing one letter at a time
                for j in range(len(currentWord)):
                    for c in range(ord('a'), ord('z') + 1):
                        nextWord = currentWord[:j] + chr(c) + currentWord[j + 1:]

                        if nextWord == endWord:
                            return transformations + 1  # Found the endWord

                        if nextWord in wordSet and nextWord not in visited:
                            visited.add(nextWord)
                            queue.append(nextWord)

            transformations += 1

        return 0  # No transformation sequence found

# Test cases
solution = WordLadderLength()

# Example 1
beginWord1 = "hit"
endWord1 = "cog"
wordList1 = ["hot", "dot", "dog", "lot", "log", "cog"]
print(solution.ladderLength(beginWord1, endWord1, wordList1))  # Output: 5

# Example 2
beginWord2 = "hit"
endWord2 = "cog"
wordList2 = ["hot", "dot", "dog", "lot", "log"]
print(solution.ladderLength(beginWord2, endWord2, wordList2))  # Output: 0

This Python code uses a similar structure as the Java solution. The WordLadderLength class represents the solution, and the ladderLength method performs BFS to find the length of the shortest transformation sequence. The provided test cases demonstrate its usage.