Problem overview
The function ladder_length takes begin_word, end_word and a vector words, and returns the number of words in the shortest chain from begin_word to end_word. Each step changes one letter, and every word after the first must be in words. When no chain exists, it returns 0.
For begin_word = "hit", end_word = "cog" and words = ["hot", "dot", "dog", "lot", "log", "cog"], the chain hit -> hot -> dot -> dog -> cog has five words, so the answer is 5. Without "cog" in the list, the answer is 0. Words have equal lengths, use lowercase letters and have no duplicates. begin_word does not have to be in the list.
Approach: search from both ends and meet in the middle
A single breadth-first search (BFS) from begin_word visits every word within distance d before it reaches the target at distance d. When each word has many neighbors, the number of words grows quickly with each level, so the last levels are the expensive ones. Searching from both ends splits one deep search into two shallow ones. Each side only goes about half as far, and the two frontiers meet in the middle.
The neighbors come from wildcard patterns, as in the previous lesson. Replacing one position of a word by * gives a pattern such as h*t, and two words are one change apart exactly when they share a pattern. The program builds a map from each pattern to the words that match it, so a word's neighbors are found with a few lookups.
Each side keeps a queue and a distance map. A side's map stores, for every word it has reached, the number of words in the chain from that side's start word up to this word, so both start words are at distance 1. When a side finds a neighbor that the other side has already reached, the chain is complete. Its length is the first side's distance to the current word plus the other side's distance to the neighbor. Both numbers include their own end of the chain, and the two words are different, so no word is counted twice.
One detail makes the answer correct: each call expands a whole level of one side, never a partial one. A chain found at the first meeting is then a shortest chain, because a shorter chain would have made the searches meet in an earlier call. The side with the smaller queue goes first, since a small level is cheap to expand.
Step by step
- Reject a missing target. If
wordsdoesn't containend_word, return 0 at once. The search from the end starts atend_wordand relies on it being a word of the graph. - Build the pattern graph in
build_graph. For each word and position,get_star_wordmakes a pattern, and the word is pushed into that pattern's bucket. - Create two queues and two distance maps, one pair per side, and seed each side with its start word at distance 1.
- Loop while both queues are non-empty. If one side runs out of words, it has explored everything it can reach without meeting the other, so no chain exists.
- Write
process_level. It receives the graph, the side's queue and distances, and the other side's distances, which it only reads. It pops exactly as many words as the queue held when the call began. That count is taken once, so words pushed during the call wait for the next level. - Look at the neighbors. For each popped word and each position, get the bucket of its pattern. For each neighbor, first check the other side: if its map has the neighbor, return the sum of the two distances.
- Otherwise extend this side. If the neighbor is new to this side, give it distance
min_dist[&word] + 1, record it and enqueue it. A level with no meeting returns 0. - Choose the side to expand in
ladder_length: the begin side when its queue is no longer than the end queue, the end side otherwise. Return the level's result if it isn't 0. - Finish with 0 when the loop ends.
The solution in Rust
use std::collections::{HashMap, VecDeque};
impl Solution {
fn get_star_word(word: &str, i: usize) -> String {
let mut s = word.to_string();
s.replace_range(i..i + 1, "*");
s
}
fn build_graph(words: &[String]) -> HashMap<String, Vec<String>> {
let mut graph: HashMap<String, Vec<String>> = HashMap::new();
for word in words {
for i in 0..word.len() {
let star_word = Self::get_star_word(word, i);
graph.entry(star_word).or_default().push(word.clone());
}
}
graph
}
fn process_level(
graph: &HashMap<String, Vec<String>>,
queue: &mut VecDeque<String>,
min_dist: &mut HashMap<String, i32>,
other_min_dist: &HashMap<String, i32>,
) -> i32 {
for _ in 0..queue.len() {
if let Some(word) = queue.pop_front() {
for i in 0..word.len() {
let star_word = Self::get_star_word(&word, i);
let neighbors = graph.get(&star_word).cloned().unwrap_or_default();
for next_word in neighbors {
if other_min_dist.contains_key(&next_word) {
return min_dist[&word] + other_min_dist[&next_word];
}
if !min_dist.contains_key(&next_word) {
let dist = min_dist[&word] + 1;
min_dist.insert(next_word.clone(), dist);
queue.push_back(next_word);
}
}
}
}
}
0
}
fn ladder_length(begin_word: String, end_word: String, words: Vec<String>) -> i32 {
if !words.contains(&end_word) {
return 0;
}
let graph = Self::build_graph(&words);
let mut begin_queue: VecDeque<String> = VecDeque::new();
let mut end_queue: VecDeque<String> = VecDeque::new();
let mut begin_min_dist: HashMap<String, i32> = HashMap::new();
let mut end_min_dist: HashMap<String, i32> = HashMap::new();
begin_queue.push_back(begin_word.clone());
end_queue.push_back(end_word.clone());
begin_min_dist.insert(begin_word, 1);
end_min_dist.insert(end_word, 1);
while !begin_queue.is_empty() && !end_queue.is_empty() {
let result = if begin_queue.len() <= end_queue.len() {
Self::process_level(&graph, &mut begin_queue, &mut begin_min_dist, &end_min_dist)
} else {
Self::process_level(&graph, &mut end_queue, &mut end_min_dist, &begin_min_dist)
};
if result != 0 {
return result;
}
}
0
}
}
Rust details worth a closer look:
- Shared and mutable borrows.
process_leveltakes&HashMapfor what it reads and&mutfor the queue and map it changes. The calls pass&mut begin_queueand&mut begin_min_disttogether with&end_min_dist. These are different variables, so Rust allows a mutable borrow of one next to a shared borrow of another. - The range is evaluated once.
for _ in 0..queue.len()computes the length before the loop begins. The queue grows while the loop runs, but the number of iterations stays fixed. That is what makes it a level-by-level search. The loop variable is_because the counter itself isn't used. if letonpop_front().pop_frontreturns anOption. The loop runs once per word that was in the queue, so the value is alwaysSome, andif letunpacks it without anunwrap.- Early return from deep inside.
returnleavesprocess_levelfrom within three nested loops, and the final0without a semicolon is the value of an ordinary level. ifas an expression.let result = if ... { ... } else { ... };givesresultthe value of whichever call runs. The calls inside the branches have no semicolon, and the semicolon after the closing brace ends thelet.- Ownership of the start words. The code clones
begin_wordandend_wordfor the queues and moves the originals into the maps, because each collection needs its own owned string. - Why
0is a safe signal. A chain has at least two words, since the start and end words differ, so a real answer is never 0.
Complexity
Let N be the number of words and L their length.
Time: O(N · L²). Building the graph costs O(N · L²): N · L patterns, each built and hashed in O(L). The searches expand each word at most once per side, with L pattern lookups of cost O(L) each, and a bucket holds at most 26 words. That is the worst case. In practice the two searches stop when they meet, so each explores only about half of the distance and often far fewer words than a single search from one end.
Space: O(N · L²). The graph stores up to N · L patterns and word copies of length L. The two queues and two maps hold O(N · L).
Edge cases and common mistakes
end_wordnot in the list. The first check returns 0 before any search.begin_wordnot in the list. The end side can never step onto it, because it is in no bucket. Only the begin side's expansion links it to the other words, and that is why the tie inbegin_queue.len() <= end_queue.len()goes to the begin side. Withbegin_word = "hot",end_word = "dot"andwords = ["dot"]the answer is 2. If the comparison were<, the end side would expand first on the tie and the same input would give 0.- Expanding single words instead of levels. The searches could then meet through a longer chain while a shorter one still waits in a queue. Expanding whole levels avoids that.
- Counting a word twice. The sum is
min_dist[&word] + other_min_dist[&next_word], with no extra+ 1or- 1, because each distance counts its own start word and the two words are different. - Disconnected words. When the two sides cannot reach each other, one side eventually empties its queue, and the loop ends with 0.
Testing
begin_word = "hit",end_word = "cog"andwords = ["hot", "dot", "dog", "lot", "log", "cog"]give 5.- The same call without
"cog"gives 0. begin_word = "hot",end_word = "dot"andwords = ["dot"]give 2.begin_word = "ab",end_word = "cd"andwords = ["ad", "cd"]give 3.
