Word Ladder

• Convert wordList to a Set for efficient lookups and removal. Let's call it wordSet.
• If endWord is not in wordSet, a transformation is impossible, so return 0.
• Initialize a queue for BFS and add beginWord.
• Initialize a variable level = 1 to track the length of the transformation sequence.
• Start the BFS loop which continues as long as the queue is not empty.
• In each iteration of the loop, process all nodes at the current level. The number of nodes is the current size of the queue.
• For each currentWord dequeued from the queue:
  • Iterate through all words in the wordSet.
  • For each nextWord, check if it's a neighbor of currentWord (differs by exactly one letter).
  • If nextWord is a neighbor:
    • If nextWord is the endWord, the shortest path is found. Return level + 1.
    • Otherwise, add nextWord to the queue for the next level's processing.
    • Crucially, remove nextWord from wordSet to mark it as visited, preventing cycles and redundant checks.
• After processing all words at the current level, increment level.
• If the queue becomes empty and endWord has not been reached, it means no such path exists. Return 0.

The fundamental idea is to perform a Breadth-First Search (BFS) starting from beginWord. BFS is guaranteed to find the shortest path in terms of the number of edges (or in this case, words) in an unweighted graph.

We use a queue to manage the words to visit and a set to keep track of words in the dictionary that we haven't visited yet. The search proceeds in levels, where each level corresponds to an increase in the transformation sequence length.

For every word we take from the queue, we search for its neighbors. A neighbor is a word in the dictionary that differs by only one character. The brute-force part is this search: we linearly scan through all available words in the dictionary and compare them character by character with the current word. If we find a neighbor, we add it to the queue and remove it from the dictionary set to avoid revisiting it. The search terminates and returns the current length (level + 1) as soon as we find the endWord. If the queue empties before the endWord is found, no path exists.

1class Solution {2    public int ladderLength(String beginWord, String endWord, List<String> wordList) {3        Set<String> wordSet = new HashSet<>(wordList);4        if (!wordSet.contains(endWord)) {5            return 0;6        }7 8        Queue<String> queue = new LinkedList<>();9        queue.offer(beginWord);10        11        int level = 1;12 13        while (!queue.isEmpty()) {14            int size = queue.size();15            for (int i = 0; i < size; i++) {16                String currentWord = queue.poll();17                18                // Use an iterator to safely remove from wordSet while iterating19                Iterator<String> iterator = wordSet.iterator();20                while (iterator.hasNext()) {21                    String nextWord = iterator.next();22                    if (isOneLetterApart(currentWord, nextWord)) {23                        if (nextWord.equals(endWord)) {24                            return level + 1;25                        }26                        queue.offer(nextWord);27                        // Remove to prevent cycles and re-processing28                        iterator.remove(); 29                    }30                }31            }32            level++;33        }34 35        return 0;36    }37 38    private boolean isOneLetterApart(String s1, String s2) {39        int diff = 0;40        for (int i = 0; i < s1.length(); i++) {41            if (s1.charAt(i) != s2.charAt(i)) {42                if (++diff > 1) return false;43            }44        }45        return diff == 1;46    }47}

• Pre-computation Step:
  • Create a HashMap<String, List<String>> named allComboDict.
  • Iterate through each word in the wordList.
  • For each word, generate all its L possible generic forms by replacing one character at a time with a wildcard (e.g., *). For hot, this would be *ot, h*t, ho*.
  • For each generic form, add the original word to the list of words associated with that generic form in allComboDict.
• BFS Step:
  • Initialize a queue with a pair containing the beginWord and its level, 1.
  • Create a visited set and add beginWord to it.
  • While the queue is not empty:
    • Dequeue the current (word, level) pair.
    • Generate all L generic forms for the current word.
    • For each generic form, look up the list of matching words (neighbors) in allComboDict.
    • For each adjacentWord in this list:
      • If adjacentWord is the endWord, return level + 1.
      • If adjacentWord has not been visited, add it to the visited set and enqueue it with level + 1.

The main bottleneck of the brute-force approach is finding all words that are one transformation away. We can significantly speed this up with pre-computation.

The idea is to group all words in the dictionary that can be intermediate steps for each other. For example, dot, hot, and lot are all neighbors because they can be represented by the generic pattern *ot. We can create a hash map where the keys are these generic patterns and the values are lists of words that fit the pattern.

First, we iterate through the entire wordList and for each word, we generate all its possible generic forms (where one letter is replaced by a wildcard like *). We populate our hash map with these mappings. This pre-processing step takes O(N * L^2) time.

After the map is built, we perform a standard BFS. For any given word, instead of scanning the whole dictionary, we just generate its L generic forms, look them up in our map, and instantly get a list of all its neighbors. This makes the neighbor-finding step within the BFS much more efficient.

1import javafx.util.Pair; // Or define a custom Pair class2 3class Solution {4    public int ladderLength(String beginWord, String endWord, List<String> wordList) {5        Set<String> wordSet = new HashSet<>(wordList);6        if (!wordSet.contains(endWord)) {7            return 0;8        }9 10        Map<String, List<String>> allComboDict = new HashMap<>();11        int L = beginWord.length();12 13        wordList.forEach(word -> {14            for (int i = 0; i < L; i++) {15                String genericWord = word.substring(0, i) + "*" + word.substring(i + 1, L);16                List<String> transformations = allComboDict.getOrDefault(genericWord, new ArrayList<>());17                transformations.add(word);18                allComboDict.put(genericWord, transformations);19            }20        });21 22        Queue<Pair<String, Integer>> queue = new LinkedList<>();23        queue.offer(new Pair<>(beginWord, 1));24 25        Set<String> visited = new HashSet<>();26        visited.add(beginWord);27 28        while (!queue.isEmpty()) {29            Pair<String, Integer> node = queue.poll();30            String word = node.getKey();31            int level = node.getValue();32 33            for (int i = 0; i < L; i++) {34                String genericWord = word.substring(0, i) + "*" + word.substring(i + 1, L);35 36                for (String adjacentWord : allComboDict.getOrDefault(genericWord, new ArrayList<>())) {37                    if (adjacentWord.equals(endWord)) {38                        return level + 1;39                    }40                    if (!visited.contains(adjacentWord)) {41                        visited.add(adjacentWord);42                        queue.offer(new Pair<>(adjacentWord, level + 1));43                    }44                }45            }46        }47        return 0;48    }49}

• Put wordList into a Set for O(1) lookups.
• Initialize two queues: queueBegin with beginWord and queueEnd with endWord.
• Initialize two Maps to track visited nodes and their levels from each direction: visitedBegin with {beginWord: 1} and visitedEnd with {endWord: 1}.
• While both queues are non-empty:
  • To keep the search balanced, choose the smaller of the two queues to expand for the current level.
  • Dequeue a word from the chosen queue. Let its level be level.
  • Generate all possible one-letter-different neighbors of word.
  • For each neighbor:
    • Check if this neighbor has been visited by the other search (i.e., exists in the other visited map). If yes, a path has been found. The total length is level from the current search plus the level stored in the other map. Return this sum.
    • If the neighbor is a valid word (in the wordSet) and has not been visited by the current search, add it to the current visited map with level + 1 and enqueue it.
• If one of the queues becomes empty, it means the two searches cannot meet, so no path exists. Return 0.

Bidirectional search is a powerful optimization for shortest path problems. Instead of exploring outwards from a single point, we start two BFS searches simultaneously, one from the beginWord and one from the endWord.

The search proceeds in levels, but we alternate between expanding the frontier from the beginning and the end. To be most efficient, we always choose to expand the smaller of the two frontiers. This helps to keep the two search areas roughly the same size and ensures we meet in the middle as quickly as possible.

A path is found when a word expanded from one search is discovered to have already been visited by the other search. When this happens, we can combine the path from the start to the meeting point and the path from the end to the meeting point to form the full shortest path. The total length is the sum of the levels from both searches.

This implementation uses an efficient on-the-fly neighbor generation technique. For a given word, it iterates through each character position, tries all 26 possible lowercase letters, and checks if the resulting new word exists in the dictionary. This avoids the O(N * L^2) space complexity of the pre-computation approach, making this method optimal in both time and space.

1class Solution {2    public int ladderLength(String beginWord, String endWord, List<String> wordList) {3        Set<String> wordSet = new HashSet<>(wordList);4        if (!wordSet.contains(endWord)) {5            return 0;6        }7 8        Queue<String> queueBegin = new LinkedList<>();9        Queue<String> queueEnd = new LinkedList<>();10        11        Map<String, Integer> visitedBegin = new HashMap<>();12        Map<String, Integer> visitedEnd = new HashMap<>();13 14        queueBegin.offer(beginWord);15        visitedBegin.put(beginWord, 1);16        17        queueEnd.offer(endWord);18        visitedEnd.put(endWord, 1);19 20        while (!queueBegin.isEmpty() && !queueEnd.isEmpty()) {21            // Always expand the smaller queue to keep the search balanced22            if (queueBegin.size() <= queueEnd.size()) {23                int result = visitNode(queueBegin, visitedBegin, visitedEnd, wordSet);24                if (result > -1) return result;25            } else {26                int result = visitNode(queueEnd, visitedEnd, visitedBegin, wordSet);27                if (result > -1) return result;28            }29        }30        return 0;31    }32 33    private int visitNode(Queue<String> queue, Map<String, Integer> visited, Map<String, Integer> otherVisited, Set<String> wordSet) {34        String word = queue.poll();35        int level = visited.get(word);36        int L = word.length();37 38        char[] chars = word.toCharArray();39        for (int i = 0; i < L; i++) {40            char originalChar = chars[i];41            for (char c = 'a'; c <= 'z'; c++) {42                chars[i] = c;43                String adjacentWord = new String(chars);44 45                if (otherVisited.containsKey(adjacentWord)) {46                    return level + otherVisited.get(adjacentWord);47                }48 49                if (wordSet.contains(adjacentWord) && !visited.containsKey(adjacentWord)) {50                    visited.put(adjacentWord, level + 1);51                    queue.offer(adjacentWord);52                }53            }54            chars[i] = originalChar; // backtrack55        }56        return -1;57    }58}