Word Ladder
Hard · Graphs · Explanation and code example
Meet In The Middle (BFS)
How it works
Standard BFS explores exponentially more nodes as distance increases. By running two BFS searches simultaneously from beginWord and endWord, we can meet in the middle, effectively halving the search depth and dramatically reducing the search space. At each step, we expand the smaller frontier to balance the workload.
Steps
- Initialize two queues: one from beginWord and one from endWord.
- Maintain two maps tracking the distance from each end for visited words.
- Always expand the smaller queue to minimize work.
- For each word, generate neighbors by changing one character at a time.
- If a neighbor is already visited by the other search, return the sum of both distances.
- Otherwise, if unvisited by the current search, add to queue and record distance.
Complexity
- Time complexity:
O(m ^ 2 * n) - Space complexity:
O(m ^ 2 * n)
Where
nis the number of words andmis the length of the word.
Things to watch for
Returning Distance Instead of Word Count
The problem asks for the number of words in the transformation sequence, not the number of transformations (edges). Off-by-one errors occur when returning the edge count instead of the node count.
Forgetting to Check if endWord Exists in wordList
If the endWord is not in the word list, transformation is impossible. Skipping this check leads to unnecessary BFS traversal and potential incorrect results.
Not Marking Words as Visited Before Adding to Queue
Adding a word to the queue without immediately marking it visited allows the same word to be added multiple times from different neighbors, causing duplicate processing and incorrect distance calculations.
Comparing Characters at Same Position in Neighbor Generation
When generating neighbor words by changing one character, forgetting to skip the original character at each position generates the same word as a "neighbor."
Using DFS Instead of BFS for Shortest Path
DFS finds a path but not necessarily the shortest. BFS guarantees the shortest path in an unweighted graph by exploring all nodes at distance k before distance k+1.
Python code example
from typing import List
from collections import deque
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList or beginWord == endWord:
return 0
m = len(wordList[0])
wordSet = set(wordList)
qb, qe = deque([beginWord]), deque([endWord])
fromBegin, fromEnd = {beginWord: 1}, {endWord: 1}
while qb and qe:
if len(qb) > len(qe):
qb, qe = qe, qb
fromBegin, fromEnd = fromEnd, fromBegin
for _ in range(len(qb)):
word = qb.popleft()
steps = fromBegin[word]
for i in range(m):
for c in range(97, 123):
if chr(c) == word[i]:
continue
nei = word[:i] + chr(c) + word[i + 1:]
if nei not in wordSet:
continue
if nei in fromEnd:
return steps + fromEnd[nei]
if nei not in fromBegin:
fromBegin[nei] = steps + 1
qb.append(nei)
return 0
C++ code example
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
if (find(wordList.begin(), wordList.end(), endWord) == wordList.end() ||
beginWord == endWord)
return 0;
int m = wordList[0].size();
unordered_set<string> wordSet(wordList.begin(), wordList.end());
queue<string> qb, qe;
unordered_map<string, int> fromBegin, fromEnd;
qb.push(beginWord);
qe.push(endWord);
fromBegin[beginWord] = 1;
fromEnd[endWord] = 1;
while (!qb.empty() && !qe.empty()) {
if (qb.size() > qe.size()) {
swap(qb, qe);
swap(fromBegin, fromEnd);
}
int size = qb.size();
for (int k = 0; k < size; k++) {
string word = qb.front();
qb.pop();
int steps = fromBegin[word];
for (int i = 0; i < m; i++) {
for (char c = 'a'; c <= 'z'; c++) {
if (c == word[i])
continue;
string nei = word.substr(0, i) +
c + word.substr(i + 1);
if (!wordSet.count(nei))
continue;
if (fromEnd.count(nei))
return steps + fromEnd[nei];
if (!fromBegin.count(nei)) {
fromBegin[nei] = steps + 1;
qb.push(nei);
}
}
}
}
}
return 0;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.