127. Word Ladder

HardBreadth-First SearchHash TableString
Leetcode Link

Problem Description

The challenge is to find the shortest series of transformations to change one given word into another, using a set of allowed transformations. Each transformation changes just one letter at a time and the resulting word must be in a provided list of words, known as the wordList. Important rules to note are that each word in the transformation sequence must be in the wordList (except for the beginWord), the endWord must be achieved through these transformations, and each transformed word can differ by only a single letter from the previous word in the sequence. The goal is to find the minimum number of transformations required to achieve this. If it's not possible to transform the beginWord to the endWord, the solution should return 0.

Intuition

The intuition behind the solution to this problem is to visualize the transformations as steps in a graph traversal, where each node is a word, and each edge represents a valid single-letter transformation. Since the objective is to find the shortest transformation sequence, Breadth-First Search (BFS) is a natural fit. BFS explores the neighbor nodes level by level, which guarantees that the first time we visit the target node (endWord in this case), we've taken the minimum number of steps to get there.

The solution employs a bi-directional BFS for improved efficiency. Instead of searching from beginWord to endWord, we simultaneously search from both beginWord and endWord, meeting somewhere in the middle. This can significantly reduce the search space and hence the time complexity, especially when the wordList is large.

Each letter of the current word is replaced sequentially with every letter from 'a' to 'z', and the new word is checked to see if it's a valid transformation (i.e., in wordList). If it is valid and has not been encountered before (not in the visited map), we add it to the next level of search.

The algorithm keeps two queues and two maps, each representing the current level of the BFS search from the start and the end. When a new word is found in both ends' maps, it means we have found a connection between the start and the end, thus having the minimum number of transformations.

If the two searches meet, we calculate the total number of transformations by adding the number of steps taken from both sides. If we exhaust all possibilities without the two searches meeting, no valid transformation sequence exists, and the function returns 0.

Learn more about Breadth-First Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Solution Approach

The solution applies a bi-directional Breadth-First Search (BFS) algorithm. The key components and processes in the implementation include:

  • Data Structures: For efficient access and search operations, the algorithm utilizes sets and dictionaries (maps). Specifically, a set named words is used to store the wordList for constant-time word validation. Two maps (m1 and m2) track the number of steps taken from beginWord and endWord to any given word encountered during the search. Two queues (q1 and q2) maintain the current frontier of words at each level of the BFS from the respective starting points.

  • Initialization: The algorithm initializes the maps with the beginWord and endWord as keys and their values set to 0, because 0 steps have been taken initially. Similarly, the queues are initialized with the beginWord and endWord.

  • BFS Function: The core of the solution is in the extend function which performs one level of BFS for either the begin queue (q1) or end queue (q2). It iterates over all words at the current frontier, and for each word:

    1. It tries replacing every letter position with every alphabet letter from 'a' to 'z'.
    2. If the new word is found in words and hasn’t been seen in its own direction's map (to avoid cycles), it proceeds.
    3. It checks if the new word is present in the opposite direction's map (m2), meaning a connection is established, and returns the total number of steps.
    4. If the connection is not found, the new word is added to the map with an incremented step count, and to the queue for further search.

  • Bi-directional BFS Execution: The algorithm alternates between extending q1 and q2, always choosing the smaller queue to extend next. This is done to keep the search space as small as possible at any given time.

  • Termination and Result Calculation: The searches continue in a bidirectional fashion until either:

    • A connection is found between the two searches, signifying a successful transformation sequence. The total number of steps is returned.
    • Both queues become empty, meaning all possible paths have been explored without finding a connection between beginWord and endWord. In this case, the function returns 0.

With this approach, we can effectively find the shortest path (minimum number of transformations) through the search space created by permissible word transformations, or determine that such a path does not exist.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Example Walkthrough

Let's suppose we have the following scenario:

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

We want to transform "hit" into "cog". Each transformation changes one letter, so we take only valid transformation steps from the wordList. Here's how the solution works:

Initialization

  • words is a set containing the wordList: {"hot", "dot", "dog", "lot", "log", "cog"}
  • Maps m1 and m2 are created with beginWord and endWord as keys respectively: m1 = {"hit": 1}, m2 = {"cog": 1}
  • Queues q1 and q2 are initialized with beginWord and endWord: q1 = ["hit"], q2 = ["cog"]

BFS Execution

  1. First Level Search From beginWord ("hit")

    • The algorithm considers "hit" and tries changing each letter to every letter from 'a' to 'z'.
    • It finds "hot" as a valid word from the words set, which is not present in m1.
    • "hot" is added to the map with a step count of 2 (m1 = {"hit": 1, "hot": 2}) and added to the q1.

  2. First Level Search From endWord ("cog")

    • Similar steps are performed for "cog".
    • It finds "dog" and "log" as valid transformations.
    • They're added to m2 and q2: m2 = {"cog": 1, "dog": 2, "log": 2}.

  3. Second Level Search From "hot"

    • Now, "hot" is the next item in q1.
    • It finds "dot" and "lot" as valid transformations.
    • They're added to m1 and q1 for the next level search.
    • m1 = {"hit": 1, "hot": 2, "dot": 3, "lot": 3}.

  4. Second Level Search From "dog" and "log"

    • For "dog", one possible transformation is "dot" which is found in m1.
    • This indicates that we've found a connection through "dot".
    • The current counts from both ends through this connection are m1["dot"] = 3 and m2["dog"] = 2, so the total is 3 + 2 - 1 = 4. (We subtract 1 because "dot" was counted from both sides.)

Termination and Result

  • Since we've found a connection through "dot", we can stop the search. The minimum transformation sequence is identified: "hit" -> "hot" -> "dot" -> "dog" -> "cog"
  • The minimum number of transformations required for "hit" to "cog" is 4.

This example illustrates how bi-directional BFS operates on both ends, finding the optimal path with a minimal number of steps for the word transformation problem.

Solution Implementation

1from collections import deque
2
3class Solution:
4    def ladderLength(self, beginWord: str, endWord: str, wordList: list[str]) -> int:
5        # Helper function to attempt to transform every word into all possible single-letter variations
6        # and to see if we can connect to the opposite side.
7        def attempt_extend(current_mappings, opposite_mappings, queue):
8            for _ in range(len(queue)):
9                # get the next word in the queue
10                word = queue.popleft()
11                word_step_count = current_mappings[word]
12                word_list = list(word)
13                # try changing every letter in the word to find a match
14                for i in range(len(word_list)):
15                    original_char = word_list[i]
16                    # replace the current character with all other possible characters
17                    for j in range(26):
18                        word_list[i] = chr(ord('a') + j)
19                        transformed_word = ''.join(word_list)
20                        # skip if the word has already been visited by the same front or doesn't exist in wordList
21                        if transformed_word in current_mappings or transformed_word not in words:
22                            continue
23                        # if the transformed word exists on the opposite front, return the total step count
24                        if transformed_word in opposite_mappings:
25                            return word_step_count + 1 + opposite_mappings[transformed_word]
26                        # otherwise, update the mapping and enqueue the transformed word
27                        current_mappings[transformed_word] = word_step_count + 1
28                        queue.append(transformed_word)
29                    # change the word back
30                    word_list[i] = original_char
31            # return -1 if no connection between the two fronts is found
32            return -1
33      
34        # Convert wordList to a set for O(1) lookups.
35        words = set(wordList)
36        # Return 0 if the target word is not even in the list.
37        if endWord not in words:
38            return 0
39      
40        # Two-ended BFS initialization
41        begin_queue = deque([beginWord])
42        end_queue = deque([endWord])
43        begin_mappings = {beginWord: 0}
44        end_mappings = {endWord: 0}
45      
46        # Execute BFS from both ends
47        while begin_queue and end_queue:
48            # Always extend the smaller front
49            if len(begin_queue) <= len(end_queue):
50                result = attempt_extend(begin_mappings, end_mappings, begin_queue)
51            else:
52                result = attempt_extend(end_mappings, begin_mappings, end_queue)
53          
54            # If a connection is found, return the total number of steps
55            if result != -1:
56                return result + 1
57      
58        # Return 0 if no connection has been found
59        return 0
60
1import java.util.*;
2
3public class Solution {
4    private Set<String> wordSet;
5
6    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
7        // Initialize the word set with the given word list
8        wordSet = new HashSet<>(wordList);
9        // If the endWord is not in the wordList, return 0 as no ladder exists
10        if (!wordSet.contains(endWord)) {
11            return 0;
12        }
13        // Use two queues to implement bidirectional BFS
14        Queue<String> queueBegin = new ArrayDeque<>();
15        Queue<String> queueEnd = new ArrayDeque<>();
16        // Maps to keep track of the path lengths from the begin and end words
17        Map<String, Integer> visitedBegin = new HashMap<>();
18        Map<String, Integer> visitedEnd = new HashMap<>();
19        // Initialize the queues and maps
20        queueBegin.offer(beginWord);
21        queueEnd.offer(endWord);
22        visitedBegin.put(beginWord, 1); // The step count starts at 1
23        visitedEnd.put(endWord, 1); 
24
25        // Perform BFS until one of the queues is empty
26        while (!queueBegin.isEmpty() && !queueEnd.isEmpty()) {
27            // Always extend the smaller queue in the current iteration
28            int result = queueBegin.size() <= queueEnd.size() ?
29                extendQueue(visitedBegin, visitedEnd, queueBegin) :
30                extendQueue(visitedEnd, visitedBegin, queueEnd);
31            // If a connection is found, return the total length of the path
32            if (result != -1) {
33                return result;
34            }
35        }
36        // If no path is found, return 0
37        return 0;
38    }
39
40    private int extendQueue(Map<String, Integer> visitedOne, Map<String, Integer> visitedOther, Queue<String> queue) {
41        // Process each word in the current layer
42        for (int i = queue.size(); i > 0; --i) {
43            String currentWord = queue.poll();
44            int currentStep = visitedOne.get(currentWord);
45            char[] characters = currentWord.toCharArray();
46            // Try changing every character to make new words
47            for (int j = 0; j < characters.length; ++j) {
48                char originalChar = characters[j];
49                for (char ch = 'a'; ch <= 'z'; ++ch) {
50                    characters[j] = ch;
51                    String newWord = new String(characters);
52                    // Skip if the new word is not in the word set or already visited
53                    if (!wordSet.contains(newWord) || visitedOne.containsKey(newWord)) {
54                        continue;
55                    }
56                    // If the new word is in the other visited map, a path is found
57                    if (visitedOther.containsKey(newWord)) {
58                        return currentStep + visitedOther.get(newWord);
59                    }
60                    // Otherwise, add the new word to the queue and visited map
61                    queue.offer(newWord);
62                    visitedOne.put(newWord, currentStep + 1);
63                }
64                // Restore the original character
65                characters[j] = originalChar;
66            }
67        }
68        // If no progress is made in this direction, return -1
69        return -1;
70    }
71}
72
1#include <unordered_set>
2#include <unordered_map>
3#include <vector>
4#include <queue>
5#include <string>
6
7class Solution {
8public:
9    // The main function that starts the bidirectional BFS
10    int ladderLength(std::string beginWord, std::string endWord, std::vector<std::string>& wordList) {
11        // Initialize a set with the words for fast lookup
12        std::unordered_set<std::string> words(wordList.begin(), wordList.end());
13        // If the end word is not in the set, no transformation sequence exists
14        if (!words.count(endWord)) return 0;
15
16        // Two queues for the bidirectional BFS
17        std::queue<std::string> queueBegin{{beginWord}};
18        std::queue<std::string> queueEnd{{endWord}};
19
20        // Mapping from word to its number of steps from the begin word or end word
21        std::unordered_map<std::string, int> stepsFromBegin;
22        std::unordered_map<std::string, int> stepsFromEnd;
23
24        // Initial steps counts for beginWord and endWord
25        stepsFromBegin[beginWord] = 1;
26        stepsFromEnd[endWord] = 1;
27
28        // Bidirectional BFS
29        while (!queueBegin.empty() && !queueEnd.empty()) {
30            // Choose the direction with the smaller frontier for extension
31            int result = queueBegin.size() <= queueEnd.size()
32                ? extendQueue(stepsFromBegin, stepsFromEnd, queueBegin, words)
33                : extendQueue(stepsFromEnd, stepsFromBegin, queueEnd, words);
34
35            if (result != -1) return result; // If paths meet, return the result
36        }
37        return 0; // If no path is found, return 0
38    }
39
40    // Extend one level of BFS, updating the queue and steps count
41    int extendQueue(std::unordered_map<std::string, int>& currentSteps, 
42                    std::unordered_map<std::string, int>& oppositeSteps, 
43                    std::queue<std::string>& currentQueue, 
44                    std::unordered_set<std::string>& words) {
45      
46        for (int i = currentQueue.size(); i > 0; --i) {
47            std::string word = currentQueue.front();
48            int step = currentSteps[word];
49            currentQueue.pop();
50
51            // Try to transform each position in the word
52            for (int j = 0; j < word.size(); ++j) {
53                char originalChar = word[j];
54
55                // Replace the current character with all possible characters
56                for (char c = 'a'; c <= 'z'; ++c) {
57                    word[j] = c;
58                    // Continue if the transformed word is the same or not in the word set
59                    if (!words.count(word) || currentSteps.count(word)) continue;
60                    // If the transformed word is in the opposite steps, a connection is found
61                    if (oppositeSteps.count(word)) return step + oppositeSteps[word];
62
63                    // Otherwise, add the transformed word into the current steps and queue
64                    currentSteps[word] = step + 1;
65                    currentQueue.push(word);
66                }
67
68                // Change back to the original character before trying the next position
69                word[j] = originalChar;
70            }
71        }
72        return -1;
73    }
74};
75
1// Import necessary TS/JS collections
2import { Queue } from 'queue'; // Placeholder for a Queue implementation
3import { Set } from 'collectionsjs'; // Placeholder for a Set implementation
4import { Map } from 'collectionsjs'; // Placeholder for a Map implementation
5
6// Function to start the bidirectional BFS
7function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
8  const words = new Set<string>(wordList);
9  if (!words.has(endWord)) return 0; // If the end word is not in the set, no transformation sequence exists.
10
11  // Two queues for the bidirectional BFS
12  const queueBegin = new Queue<string>();
13  const queueEnd = new Queue<string>();
14
15  // Mapping from word to its number of steps from the begin word or end word
16  const stepsFromBegin = new Map<string, number>();
17  const stepsFromEnd = new Map<string, number>();
18
19  // Initial steps counts for beginWord and endWord
20  stepsFromBegin.set(beginWord, 1);
21  stepsFromEnd.set(endWord, 1);
22
23  queueBegin.enqueue(beginWord);
24  queueEnd.enqueue(endWord);
25
26  // Execution of bidirectional BFS
27  while (!queueBegin.isEmpty() && !queueEnd.isEmpty()) {
28    // Choose the direction with the smaller frontier for extension
29    const result = queueBegin.length <= queueEnd.length ?
30      extendQueue(stepsFromBegin, stepsFromEnd, queueBegin, words) :
31      extendQueue(stepsFromEnd, stepsFromBegin, queueEnd, words);
32
33    if (result != -1) return result; // If paths meet, return the result
34  }
35  return 0; // If no path is found, return 0
36}
37
38// Extend one level of BFS, updating the queue and steps count
39function extendQueue(
40  currentSteps: Map<string, number>,
41  oppositeSteps: Map<string, number>,
42  currentQueue: Queue<string>,
43  words: Set<string>
44): number {
45
46  const size = currentQueue.length;
47  for (let i = 0; i < size; i++) {
48    const word: string = currentQueue.dequeue();
49    const step: number = currentSteps.get(word);
50
51    // Attempt transformations for each position in the word
52    for (let j = 0; j < word.length; j++) {
53      const originalChar = word[j];
54      // Construct new word variants by replacing the current character
55      let transformedWord = word;
56
57      for (let c = 0; c < 26; c++) {
58        transformedWord = replaceAt(transformedWord, j, String.fromCharCode(97 + c));
59
60        // Skip if the transformed word is the same or not in word set
61        if (!words.has(transformedWord) || currentSteps.has(transformedWord)) continue;
62      
63        // If the transformed word is in the opposite steps, a connection is found
64        if (oppositeSteps.has(transformedWord)) return step + oppositeSteps.get(transformedWord);
65
66        // Add the transformed word into the current steps and queue
67        currentSteps.set(transformedWord, step + 1);
68        currentQueue.enqueue(transformedWord);
69      }
70    }
71  }
72
73  return -1; // Return -1 if no connection has been found on this level
74}
75
76// Replace character at specific index in a string
77function replaceAt(s: string, index: number, character: string): string {
78  return s.substr(0, index) + character + s.substr(index + character.length);
79}
80
Not Sure What to Study? Take the 2-min Quiz：

Which of these properties could exist for a graph but not a tree?

Time and Space Complexity

The provided code solves the Word Ladder problem using a bidirectional Breadth-First Search (BFS) technique. The main idea is to simultaneously search from the beginning word and the end word towards each other and meet in the middle, which can significantly reduce the search space.

Time Complexity:

The time complexity of the algorithm depends on the number of words (N) and the length of each word (L). In the worst case, we might end up visiting all the words in the list, and for each word, we try changing each letter (where there are 26 possibilities for each letter change). Therefore, the time complexity can be expressed as O(L * 26 * N).

However, the bidirectional search potentially halves the search space since we progress from both ends and stop when we meet in the middle, which can reduce the time complexity to approximately O(L * 26 * N / 2), though in Big O notation, we still represent it as O(L * 26 * N) since constant factors are not considered.

Space Complexity:

The space complexity is primarily dictated by the additional data structures used to hold the intermediate states, such as the queues (q1 and q2) and the visited nodes dictionaries (m1 and m2). Since we store at most every word in these structures, the space complexity is O(N). The character list conversion of each word and the generation of all possible one-letter variations also use space but do not exceed the complexity arising from the queues and visited nodes dictionaries.

In summary:

  • Time Complexity: O(L * 26 * N)
  • Space Complexity: O(N)

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which two pointer techniques do you use to check if a string is a palindrome?

Recommended Readings

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫