Problem overview
The function ladder_length receives a begin_word, an end_word and a vector words that acts as a dictionary. It must return the length of the shortest chain of words that starts at begin_word and ends at end_word, where each word differs from the previous one in exactly one letter and every word after the first is in words. If no chain exists, it returns 0.
The length counts both ends. With begin_word = "hit", end_word = "cog" and words = ["hot", "dot", "dog", "lot", "log", "cog"], one shortest chain is hit -> hot -> dot -> dog -> cog. It has five words and four letter changes, so the answer is 5. If "cog" is missing from the list, the chain can never end there, so the answer is 0.
All words have the same length and contain only lowercase letters, the list has no duplicates, and the two end words are different. Note that begin_word does not have to be in the list: only the words you move to must be.
Approach: a shortest path in a word graph
Think of every word as a node, with an edge between two words that differ in exactly one position. A chain of transformations is then a path, and the question asks for the shortest path between two nodes in an unweighted graph. Breadth-first search (BFS) is the standard tool for that: it visits all words one change away, then all words two changes away, and so on. The first time it reaches a word, it has reached it by a shortest chain.
The graph is never built explicitly in this lesson. Whenever BFS takes a word out of the queue, it scans the whole list and compares the word with every candidate. A candidate is a neighbor when it differs in exactly one position. This is the simplest way to find neighbors, and it costs one pass over the list per word. Later lessons on the same problem replace the scan with faster neighbor lookups.
Two maps of state keep the search correct. The queue holds words waiting to be expanded. The map min_dist stores the length of the shortest chain to each word found so far, counting both ends, so begin_word starts at 1. A word that has an entry has already been reached, so min_dist doubles as the visited set. Words are marked when they are put in the queue, not when they leave it, so no word is ever queued twice.
Step by step
- Create the queue. A
VecDeque<String>adds at the back and removes from the front in constant time, which is exactly what BFS needs. - Create
min_dist. It maps each reached word to the length of its shortest chain. - Seed the search. Push a clone of
begin_wordonto the queue and insertbegin_wordinto the map with distance 1. The clone is needed becauseinserttakes ownership of the string. - Loop until the queue is empty with
while let Some(word) = queue.pop_front(). The pattern ends the loop by itself whenpop_frontreturnsNone. - Stop at the target. Words leave the queue in order of distance, so once
end_wordcomes out, its stored distance is final and the search canbreak. - Scan the candidates. Loop over
&words, which borrows each string instead of consuming the vector, so the list can be scanned again for the next word. - Keep only true neighbors. Call the helper
num_of_changesandcontinueunless the result is exactly 1. A result of 0 means the same word, and 2 or more means too many changes. - Skip words already reached. If
min_disthas the candidate, an earlier or equally short chain to it exists. - Record and enqueue. The new word is one change further than
word, so its distance ismin_dist[&word] + 1. Store a clone of the candidate in the map and push another clone onto the queue, because each collection owns its strings. - Return the answer. Look up
end_wordin the map and fall back to 0 when it was never reached. - Write the helper as an associated function that takes two
&strvalues and returns ani32: it counts the positions where the two strings differ.
The solution in Rust
use std::collections::{HashMap, VecDeque};
impl Solution {
fn num_of_changes(first: &str, second: &str) -> i32 {
first
.chars()
.zip(second.chars())
.filter(|(a, b)| a != b)
.count() as i32
}
fn ladder_length(begin_word: String, end_word: String, words: Vec<String>) -> i32 {
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;
}
for next_word in &words {
if Self::num_of_changes(&word, next_word) != 1 {
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.clone());
}
}
*min_dist.get(&end_word).unwrap_or(&0)
}
}
Rust details worth a closer look:
- Ownership and clones. A
Stringhas one owner. The queue and the map each store their own copy of a word, which is why the code callsclone()before handing a string to the second collection. In the loop,next_wordis only a&Stringborrowed fromwords, so both stored copies must be clones. - Calling the helper.
num_of_changeshas noselfparameter, so it is called asSelf::num_of_changes. The call passes&word, a&String, where a&stris expected. Rust converts it automatically. - The iterator chain.
first.chars().zip(second.chars())pairs the characters position by position and stops at the shorter string.filter(|(a, b)| a != b)keeps the pairs that differ, andcount()returns ausize, soas i32matches the return type. With no semicolon, the chain is the function's value. For example,"hot"and"dot"give 1,"hot"and"dog"give 2, and"hot"and"hot"give 0. - Indexing the map.
min_dist[&word]panics if the key is missing. It can't be missing here, because every word in the queue was inserted into the map first. - The final line.
getreturns anOption<&i32>.unwrap_or(&0)supplies a reference to 0 when the key is absent, and the leading*turns the reference into a plaini32.
Complexity
Let N be the number of words and L their length.
Time: O(N² · L). Each word is queued at most once, because it is marked as reached when it is pushed. Each word taken from the queue is compared with all N candidates, and each comparison walks up to L characters.
Space: O(N · L). The queue and the map hold at most one copy of each word.
Edge cases and common mistakes
end_wordmissing from the list. The search never reaches it, the map has no entry, and the function returns 0.begin_wordmissing from the list. This is fine. Withbegin_word = "hot",end_word = "dot"andwords = ["dot"]the answer is 2, because the search starts frombegin_wordregardless of the list.begin_wordinside the list. It already has an entry in the map, so it is skipped as a neighbor and not queued again.- One change apart. When
end_wordis in the list and differs frombegin_wordby one letter, the answer is 2, not 1: the length counts words, not changes. - Starting the distance at 0. Then every answer is off by one. The seed distance is 1 because a chain of just
begin_wordhas one word. - Marking words as visited when they leave the queue. A word could then be pushed several times by different neighbors, and the queue and the work grow with every duplicate.
- Skipping only identical words. A candidate that differs in two or more positions is not a neighbor either, so the test is
!= 1, not== 0.
Testing
begin_word = "hit",end_word = "cog",words = ["hot", "dot", "dog", "lot", "log", "cog"]gives 5.- The same words without
"cog"give 0. begin_word = "hot",end_word = "dot",words = ["dot"]gives 2.begin_word = "ab",end_word = "cd",words = ["ad", "cd"]gives 3.
