LeetCode Hard - Word Ladder II -

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s₁ -> s₂ -> ... -> s_k such that:

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

Given two words, beginWord and endWord, and a dictionary wordList, return all the shortest transformation sequences from beginWord to endWord, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words [beginWord, s₁, s₂, ..., s_k].

Example 1:

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

Output: [[“hit”,”hot”,”dot”,”dog”,”cog”],[“hit”,”hot”,”lot”,”log”,”cog”]]

Explanation: There are 2 shortest transformation sequences: “hit” -> “hot” -> “dot” -> “dog” -> “cog” “hit” -> “hot” -> “lot” -> “log” -> “cog”

Example 2:

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

Output: []

Explanation: The endWord “cog” is not in wordList, therefore there is no valid transformation sequence.

Constraints:

1 <= beginWord.length <= 5
endWord.length == beginWord.length
1 <= wordList.length <= 500
wordList[i].length == beginWord.length
beginWord, endWord, and wordList[i] consist of lowercase English letters.
beginWord != endWord
All the words in wordList are unique.
The sum of all shortest transformation sequences does not exceed 10⁵.

Java Solution

To solve this problem, you can use Breadth-First Search (BFS) to find the shortest transformation sequences. You can build a graph where each word is a node, and there is an edge between two nodes if the corresponding words differ by a single letter. Then, perform BFS to find the shortest paths from the beginWord to the endWord.

Here’s the Java solution:

import java.util.*;

public class WordLadderII {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> result = new ArrayList<>();
        Set<String> wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(endWord)) {
            return result;  // If endWord is not in wordList, return an empty list
        }

        Map<String, List<String>> graph = new HashMap<>();
        Set<String> visited = new HashSet<>();
        Queue<List<String>> queue = new LinkedList<>();
        boolean found = false;

        // Initialize BFS queue with the start word
        queue.offer(Arrays.asList(beginWord));

        // Perform BFS
        while (!queue.isEmpty() && !found) {
            int size = queue.size();
            Set<String> currentLevelVisited = new HashSet<>();

            for (int i = 0; i < size; i++) {
                List<String> path = new ArrayList<>(Objects.requireNonNull(queue.poll()));
                String currentWord = path.get(path.size() - 1);

                // 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 (wordSet.contains(nextWord) && !visited.contains(nextWord)) {
                            currentLevelVisited.add(nextWord);
                            List<String> newPath = new ArrayList<>(path);
                            newPath.add(nextWord);
                            queue.offer(newPath);

                            // Build the graph
                            graph.computeIfAbsent(currentWord, k -> new ArrayList<>()).add(nextWord);

                            if (nextWord.equals(endWord)) {
                                found = true;
                                result.add(newPath);
                            }
                        }
                    }
                }
            }

            visited.addAll(currentLevelVisited);
        }

        return result;
    }

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

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

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

This Java code defines a WordLadderII class with the findLadders method, which uses BFS to find all the shortest transformation sequences. The provided test cases demonstrate its usage.

Python Solution

Here’s the equivalent Python solution for finding the shortest transformation sequences using Breadth-First Search (BFS):

from collections import defaultdict, deque

class WordLadderII:
    def findLadders(self, beginWord, endWord, wordList):
        result = []
        wordSet = set(wordList)
        if endWord not in wordSet:
            return result  # If endWord is not in wordList, return an empty list

        graph = defaultdict(list)
        visited = set()
        queue = deque()
        found = False

        # Initialize BFS queue with the start word
        queue.append([beginWord])

        # Perform BFS
        while queue and not found:
            size = len(queue)
            currentLevelVisited = set()

            for _ in range(size):
                path = queue.popleft()
                currentWord = path[-1]

                # 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 in wordSet and nextWord not in visited:
                            currentLevelVisited.add(nextWord)
                            newPath = path + [nextWord]
                            queue.append(newPath)

                            # Build the graph
                            graph[currentWord].append(nextWord)

                            if nextWord == endWord:
                                found = True
                                result.append(newPath)

            visited.update(currentLevelVisited)

        return result

# Test cases
solution = WordLadderII()

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

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

This Python code uses a similar structure as the Java solution. The WordLadderII class represents the solution, and the findLadders method performs BFS to find all the shortest transformation sequences. The provided test cases demonstrate its usage.

LeetCode Hard – Word Ladder II

Java Solution

Python Solution

Leave a Reply Cancel reply