#127

Hard

LeetCode Problem Workspace

Word Ladder

Find the shortest transformation sequence from a start word to an end word, with each word in the sequence differing by only one letter.

hash table string breadth first search

Problem Statement

Given a start word beginWord, an end word endWord, and a list of words wordList, the task is to find the number of words in the shortest transformation sequence from beginWord to endWord. Each transformation involves changing exactly one letter, and the new word must exist in wordList. Return the length of the sequence or 0 if no such transformation exists.

For example, given beginWord = "hit", endWord = "cog", and wordList = ["hot","dot","dog","lot","log","cog"], the sequence is "hit" -> "hot" -> "dot" -> "dog" -> "cog", and the result is 5. If the end word is not present in the list, or if no valid sequence exists, return 0.

Examples

Example 1

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

Output: 5

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

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.

Solution Approach

Breadth-First Search (BFS)

BFS is used to explore all possible transformations from the beginWord. Starting with beginWord, transform one letter at a time and check if the resulting word is in wordList. Each valid transformation is enqueued for further exploration, and we track the number of transformations. The BFS ensures that the first time we reach the endWord, it is via the shortest transformation sequence.

Hash Table for Word Lookup

A hash table (or set) is used to store the wordList, enabling quick lookups for valid transformations. This speeds up the process of checking if a word exists in the list, which is crucial in BFS. By using the hash table, we avoid repeatedly scanning the entire list, ensuring an efficient solution.

Word Transformation Logic

For each word in the BFS queue, generate all possible valid transformations by changing one letter at a time. For example, starting with 'hit', check words like 'hot', 'dot', etc. Each valid word is added to the queue and removed from the hash table to prevent revisiting. This continues until the endWord is found or all possibilities are exhausted.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the number of words and the length of each word, with BFS exploring all potential transformations. If there are n words, each of length m, the time complexity is O(n * m), where n is the number of words in wordList. The space complexity is O(n) for storing the hash table and BFS queue.

What Interviewers Usually Probe

Do you understand how BFS guarantees the shortest path in a word transformation sequence?
Can you explain why a hash table improves the performance of this problem?
Will you describe how to generate valid word transformations efficiently?

Common Pitfalls or Variants

Common pitfalls

Not checking if endWord is in the wordList before starting the BFS, leading to unnecessary computation.
Failing to track visited words properly, which can cause infinite loops or revisiting words.
Misunderstanding the need to change exactly one letter at a time, which can lead to invalid transformations.

Follow-up variants

Find the shortest transformation sequence from beginWord to endWord, but with an added constraint of a maximum transformation length.
Extend the problem to find all shortest transformation sequences from beginWord to endWord.
Modify the problem to allow transformations from beginWord to endWord without the restriction of using the given word list.

FAQ

What is the core idea behind the BFS approach for solving Word Ladder?

The BFS approach explores all possible word transformations level by level, ensuring the shortest transformation sequence is found as soon as the end word is reached.

Why is a hash table important in the Word Ladder problem?

A hash table allows constant time complexity lookups to check if a transformed word is part of the word list, significantly improving performance during BFS.

How do you handle already visited words in the Word Ladder problem?

Visited words are removed from the hash table as soon as they are processed in BFS, ensuring they are not revisited and preventing infinite loops.

What happens if the end word is not in the word list?

If the end word is not in the word list, the transformation sequence is impossible, and the function should return 0.

How do you optimize the word transformations in Word Ladder?

Word transformations are optimized by generating valid transformations (one letter at a time) and using a hash table to check if each transformation exists in the word list.

terminal

Solution

Solution 1: BFS

BFS minimum step model. This problem can be solved with naive BFS, or it can be optimized with bidirectional BFS to reduce the search space and improve efficiency.

while q1 and q2:
    if len(q1) <= len(q2):
        # Prioritize the queue with fewer elements for expansion
        extend(m1, m2, q1)
    else:
        extend(m2, m1, q2)


def extend(m1, m2, q):
    # New round of expansion
    for _ in range(len(q)):
        p = q.popleft()
        step = m1[p]
        for t in next(p):
            if t in m1:
                # Already visited before
                continue
            if t in m2:
                # The other direction has been searched, indicating that a shortest path has been found
                return step + 1 + m2[t]
            q.append(t)
            m1[t] = step + 1

Solution 2

#### Python3

while q1 and q2:
    if len(q1) <= len(q2):
        # Prioritize the queue with fewer elements for expansion
        extend(m1, m2, q1)
    else:
        extend(m2, m1, q2)


def extend(m1, m2, q):
    # New round of expansion
    for _ in range(len(q)):
        p = q.popleft()
        step = m1[p]
        for t in next(p):
            if t in m1:
                # Already visited before
                continue
            if t in m2:
                # The other direction has been searched, indicating that a shortest path has been found
                return step + 1 + m2[t]
            q.append(t)
            m1[t] = step + 1

Continue Practicing

#126 word ladder ii #433 minimum genetic mutation #721 accounts merge