Word Ladder

Question

Given two words and a dictionary, find the length of the shortest transformation sequence from start to end, changing one letter at a time. Tests BFS on implicit graphs.

Codemia · Accepted Answer

The problem at hand is a classic example of using **Breadth-First Search (BFS)** on an implicit graph. Each word in the dictionary can be thought of as a node, and an edge exists between two nodes if you can transform one word into another by changing a single letter. BFS is suitable here because it explores all possible transformations level by level, guaranteeing that the first time we reach the target word, it will be through the shortest transformation sequence. This approach is particularly efficient when we need to find the minimum distance or number of transformations.

1. **Initialization**: Start by creating a queue for BFS and a set for visited words to avoid cycles. Add the starting word to the queue and mark it as visited.

2. **BFS Loop**: While the queue is not empty:
   - Dequeue the current word and check if it matches the target word. If it does, return the transformation length (current depth).
   - For each letter in the current word, iterate through the alphabet (a-z). For each letter:
     - Create a new word by replacing the current letter with the new letter.
     - If the new word exists in the dictionary and has not been visited, add it to the queue and mark it as visited.

3. **Return -1**: If the target word is not reached after exhausting the queue, return -1 indicating no valid transformation exists.

**Example**: For start = "hit", end = "cog" and dictionary = ["hot", "dot", "dog", "lot", "log", "cog"], the transformations would be:
- hit -> hot (1)
- hot -> dot (2)
- dot -> dog (3)
- dog -> cog (4)
Thus, the shortest transformation length is 5.

```python
from collections import deque

def wordLadderLength(beginWord, endWord, wordList):
    wordSet = set(wordList)
    if endWord not in wordSet:
        return 0

queue = deque([beginWord])
    visited = set([beginWord])
    length = 1

while queue:
        for _ in range(len(queue)):
            currentWord = queue.popleft()
            if currentWord == endWord:
                return length
            for i in range(len(currentWord)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    newWord = currentWord[:i] + c + currentWord[i+1:]
                    if newWord in wordSet and newWord not in visited:
                        visited.add(newWord)
                        queue.append(newWord)
        length += 1
    return 0
```

The time complexity of this approach is O(N * M * 26), where N is the number of words in the dictionary and M is the length of each word. This is because for each word, we potentially check all 26 letters in all positions to generate new words. The space complexity is O(N) for the visited set and the queue. Given the constraints of the problem, this solution will efficiently handle typical input sizes.

1. **No Transformation Possible**: If the endWord is not in the dictionary, immediately return 0.
2. **Start Equals End**: If the beginWord is the same as the endWord, the length of the transformation sequence is 1.
3. **Single Letter Words**: If the words are single letters (e.g., 'a' to 'b'), ensure the dictionary contains both.
4. **Large Dictionary**: Ensure that the performance holds for a large set of words to avoid timeouts during testing.

Word Ladder

Google

How to Approach This

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Google Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string