DevExCode

LeetCode 126: Word Ladder II Solution

Master LeetCode problem 126 (Word Ladder II), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation

To solve this problem, we can use a bidirectional BFS approach along with backtracking to find all shortest transformation sequences from beginWord to endWord.

  1. First, we preprocess the wordList to create a map of words that can be formed by changing one character at a time. This helps in efficient retrieval of neighbors during the BFS traversal.
  2. We start BFS from both beginWord and endWord simultaneously, expanding the search in a bidirectional manner.
  3. During BFS, we maintain information about the parent nodes for each word, so that we can backtrack and construct the transformation sequences later.
  4. Once we find a common word in both BFS searches, we can construct the final transformation sequences using backtracking.
  5. Finally, we return all the shortest transformation sequences found.

Time Complexity

The time complexity of this approach is O(n * m), where n is the number of words in the wordList and m is the length of each word.

Space Complexity

The space complexity is O(n * m) for storing the preprocessed map of words and O(n) for the BFS queue.

Solution Code

class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> result = new ArrayList<>();
        Set<String> dict = new HashSet<>(wordList);
        if (!dict.contains(endWord)) return result;
        
        Map<String, List<String>> neighbors = new HashMap<>();
        Set<String> startSet = new HashSet<>();
        Set<String> endSet = new HashSet<>();
        
        startSet.add(beginWord);
        endSet.add(endWord);
        
        bfs(startSet, endSet, neighbors, dict, false);
        
        List<String> path = new ArrayList<>(Collections.singletonList(beginWord));
        backtrack(beginWord, endWord, neighbors, result, path);
        
        return result;
    }
    
    private void bfs(Set<String> startSet, Set<String> endSet, Map<String, List<String>> neighbors, Set<String> dict, boolean reverse) {
        if (startSet.isEmpty() || endSet.isEmpty()) return;
        
        if (startSet.size() > endSet.size()) {
            bfs(endSet, startSet, neighbors, dict, !reverse);
            return;
        }
        
        boolean found = false;
        Set<String> nextLevel = new HashSet<>();
        dict.removeAll(startSet);
        
        for (String word : startSet) {
            char[] chars = word.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                char original = chars[i];
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    if (chars[i] == ch) continue;
                    chars[i] = ch;
                    String newWord = new String(chars);
                    if (dict.contains(newWord)) {
                        if (endSet.contains(newWord)) found = true;
                        else nextLevel.add(newWord);
                        
                        String key = reverse ? newWord : word;
                        String value = reverse ? word : newWord;
                        neighbors.putIfAbsent(key, new ArrayList<>());
                        neighbors.get(key).add(value);
                    }
                }
                chars[i] = original;
            }
        }
        
        if (!found) bfs(nextLevel, endSet, neighbors, dict, reverse);
    }
    
    private void backtrack(String beginWord, String endWord, Map<String, List<String>> neighbors, List<List<String>> result, List<String> path) {
        if (beginWord.equals(endWord)) {
            result.add(new ArrayList<>(path));
            return;
        }
        
        if (!neighbors.containsKey(beginWord)) return;
        
        for (String neighbor : neighbors.get(beginWord)) {
            path.add(neighbor);
            backtrack(neighbor, endWord, neighbors, result, path);
            path.remove(path.size() - 1);
        }
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 126 (Word Ladder II)?

This page provides optimized solutions for LeetCode problem 126 (Word Ladder II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 126 (Word Ladder II)?

The time complexity for LeetCode 126 (Word Ladder II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 126 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 126 in Java, C++, or Python.

Back to LeetCode Solutions