Problem overview
The function ladder_length takes a begin_word, an end_word and a vector words. It returns the number of words in the shortest chain from begin_word to end_word, counting both ends, where each step changes exactly one letter and every word after the first must be in words. If there is no such chain, 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. All words have the same length and contain only lowercase letters, and begin_word itself doesn't need to be in the list.
Approach: generate the neighbors instead of searching for them
Words are nodes of a graph, and two words are connected when they differ in one position. The shortest chain is the shortest path from begin_word, so breadth-first search (BFS) fits: it reaches every word at distance 1 before any at distance 2, so the first time a word is reached, the route is a shortest one.
The simplest BFS finds the neighbors of a word by comparing it with every word in the list, which costs a pass over the whole list per word. This lesson flips the work around. A word with L letters has only L * 25 possible one-letter variations: for each position, 25 other letters. Instead of scanning the list, build each variation and ask a hash set whether it is a real word. When the list is long, 25 lookups per position are far cheaper than comparing against every entry.
The same two pieces of state as in any BFS remain. The queue holds words waiting to be expanded, and the map min_dist stores the length of the shortest chain found to each word, with begin_word at 1. A word with an entry in min_dist has been reached, so the map also works as the visited set.
Step by step
- Put the words in a
HashSet.words.into_iter().collect()moves the strings into a set, so "is this candidate a real word?" takes constant time on average. The type annotation tellscollectwhich collection to build. - Create the queue and
min_dist. AVecDeque<String>gives constant-timepush_backandpop_front, and the map records distances. - Seed the search. Push a clone of
begin_wordonto the queue, then movebegin_wordintomin_distwith distance 1. - Pop words until the queue is empty with
while let Some(word) = queue.pop_front(). - Break at the target. Words come out in order of distance, so when
end_wordis popped, its stored distance is the shortest. - Collect the word's characters into a
Vec<char>. A RustStringcan't be indexed by position, so the characters go into a vector that can. - Visit every position
iand every lettercfromb'a'tob'z'. Skip the letter that is already at that position, since it would rebuildword. - Build the candidate. Clone
chars, overwrite positioniwithcand collect the characters into aString. The clone leavescharsuntouched for the next letter. - Filter the candidate.
continueif it isn't inword_set, and again ifmin_distalready has it. - Record and enqueue. The distance is
min_dist[&word] + 1. The map gets a clone of the candidate, and the queue gets the candidate itself. - Return the result from the map, or 0 if
end_wordwas never reached.
The solution in Rust
use std::collections::{HashMap, HashSet, VecDeque};
impl Solution {
fn ladder_length(begin_word: String, end_word: String, words: Vec<String>) -> i32 {
let word_set: HashSet<String> = words.into_iter().collect();
let mut queue: VecDeque<String> = VecDeque::new();
let mut min_dist: HashMap<String, i32> = HashMap::new();
queue.push_back(begin_word.clone());
min_dist.insert(begin_word, 1);
while let Some(word) = queue.pop_front() {
if end_word == word {
break;
}
let chars: Vec<char> = word.chars().collect();
for i in 0..chars.len() {
for c in b'a'..=b'z' {
let c = c as char;
if c == chars[i] {
continue;
}
let mut next_chars = chars.clone();
next_chars[i] = c;
let next_word: String = next_chars.into_iter().collect();
if !word_set.contains(&next_word) {
continue;
}
if min_dist.contains_key(&next_word) {
continue;
}
let dist = min_dist[&word] + 1;
min_dist.insert(next_word.clone(), dist);
queue.push_back(next_word);
}
}
}
*min_dist.get(&end_word).unwrap_or(&0)
}
}
Rust details worth a closer look:
into_iter()consumes the vector. The function ownswordsand never needs it again, so moving the strings into the set avoids copying them.- Bytes versus characters.
b'a'..=b'z'is a range ofu8values, and..=includes the end, so all 26 letters are visited. The linelet c = c as char;shadows the byte with achar, which is the type stored inchars. Casting au8tocharwithasis always valid. - Why a
Vec<char>. Strings are UTF-8, and a character may take several bytes, so Rust doesn't offerword[i]. Here the words are lowercase ASCII, and collecting the characters is the simplest way to change one of them. - Borrowing for lookups.
containsandcontains_keytake references, so the code passes&next_word. That leavesnext_wordavailable to be moved into the queue at the end. - Clone, then move. The map needs an owned key, so it gets
next_word.clone(). The queue then takesnext_worditself, which is its last use. Reversing the order would be a compile error, because the value would already be moved. - The final expression.
min_dist.get(&end_word)returns anOption<&i32>,unwrap_or(&0)supplies a default reference, and*reads the number.
Complexity
Let N be the number of words and L their length.
Time: O(N · L² · 26), which is O(N · L²) for a fixed alphabet. Each word is queued at most once. Expanding it tries L positions with 25 letters each, and every candidate costs O(L) to build and hash. Compare that with the version that scans the list: it costs O(N · L) per expanded word, so the letter-by-letter version wins when N is much larger than 26 · L, and loses when the list is tiny and the words are long.
Space: O(N · L). The set, the map and the queue each hold up to N words of length L.
Edge cases and common mistakes
end_wordnot in the list. No candidate can equal it, so it never enters the map and the result is 0.begin_wordnot in the list. The search still starts from it. Withbegin_word = "hot",end_word = "dot"andwords = ["dot"]the answer is 2.- Forgetting the visited check. Without the
min_disttest, two words that are neighbors of each other would be queued again and again. - Checking only the set. Being in
word_setsays a candidate is a real word, not that it is new. Both tests are needed. - Using
b'a'..b'z'. Without the=, the letterzis never tried and any chain that needs it is missed. - Distance base. The seed distance is 1, because a chain with only
begin_wordhas one word. Starting at 0 makes every answer one too small. - Letters outside
atoz. The loop only tries lowercase letters. That matches the lesson's guarantee but would miss words with other characters.
Testing
begin_word = "hit",end_word = "cog"andwords = ["hot", "dot", "dog", "lot", "log", "cog"]give 5.- The same call without
"cog"in the list gives 0. begin_word = "hot",end_word = "dot"andwords = ["hot", "dot"]give 2.begin_word = "ab",end_word = "cd"andwords = ["ad", "cd"]give 3.
