Problem overview
The function ladder_length receives begin_word, end_word and a vector words. It returns the number of words in the shortest chain that starts at begin_word and ends at end_word, where each step changes exactly one letter and every word after the first is in words. It returns 0 when no chain exists.
With 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. If "cog" is not in the list, the answer is 0. The words share one length, contain only lowercase letters and have no duplicates, and begin_word need not be in the list.
Approach: group words by what they have in common
Treat words as nodes of a graph, with an edge between words that differ in one position. The shortest chain is then a shortest path, which breadth-first search (BFS) finds level by level. The remaining question is how to find a word's neighbors quickly.
Comparing a word with the whole list is slow, and trying all 26 letters at every position builds many strings that aren't words. This lesson uses a different observation. Replace one position of a word with *, and you get a pattern. "hot" gives *ot, h*t and ho*. Two words differ in exactly one position precisely when they share a pattern, so the neighbors of a word are the other words stored under its patterns.
For the example list, the buckets look like this:
*og ["dog", "log", "cog"]
*ot ["hot", "dot", "lot"]
do* ["dot", "dog"]
lo* ["lot", "log"]
h*t ["hot"]
ho* ["hot"]
The remaining patterns (c*g, co*, d*g, d*t, l*g, l*t) each hold a single word. The bucket *ot says that hot, dot and lot are all neighbors of each other.
The program builds this map once, from the list. After that, expanding a word needs only L lookups, one per pattern, and each bucket is short. Since the alphabet has 26 letters and the list has no duplicates, a bucket holds at most 26 words.
The BFS itself is the usual one. A queue holds words waiting to be expanded, and min_dist holds the length of the shortest chain found to each word, with begin_word at 1. An entry in min_dist also marks the word as visited.
Step by step
- Create the graph, a
HashMap<String, Vec<String>>from a pattern to the words that match it. - Loop over
&wordsand over every positioni. Borrowing the vector keeps it usable for the rest of the function. - Write the helper
get_star_word. It takes a&strand an index and returns a newString: copy the word, replace the one-character rangei..i + 1with"*", and return the copy. - Fill the buckets.
entry(star_word).or_default()returns the vector for the pattern, creating an empty one if needed, andpushadds a clone of the word. - Set up the BFS. Create the queue and
min_dist, push a clone ofbegin_wordand insertbegin_wordwith distance 1. - Pop words until the queue is empty. If the popped word is
end_word, return its distance at once: words leave the queue in order of distance, so no later chain can be shorter. - Expand the word. For each position, build the pattern and fetch the bucket.
graph.get(&star_word).cloned().unwrap_or_default()gives an owned copy of the bucket, or an empty vector when the pattern is unknown. - Visit each neighbor once. Skip it if
min_disthas it. Otherwise give it distancemin_dist[&word] + 1, store a clone in the map and push the neighbor onto the queue. - Finish with 0. If the queue empties without producing
end_word, there is no chain.
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 ladder_length(begin_word: String, end_word: String, words: Vec<String>) -> i32 {
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());
}
}
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 {
return min_dist[&word];
}
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 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);
}
}
}
0
}
}
Rust details worth a closer look:
replace_rangeworks on bytes. The rangei..i + 1is a range of byte positions, andword.len()counts bytes. For lowercase ASCII words that is the same as letters. If a word held a multi-byte character and the range cut through it,replace_rangewould panic.- Returning the copy. The last line of
get_star_wordiss, with no semicolon, so that is the returned value.to_string()madesan owned copy, so the original word is untouched. - The call syntax. The helper has no
self, so it is called asSelf::get_star_word. In the building loop,wordis a&Stringand converts to&strautomatically. In the BFS loop,wordis an ownedString, so the call passes&word. or_default(). For aVecvalue it inserts an empty vector when the key is missing and returns a mutable reference to the vector, which is why.push(...)can follow directly.- Why clone the bucket. The loop moves each neighbor into the queue, and that needs owned strings. A reference into
graphwould only lend them. Cloning also meansbegin_wordcan be expanded even though it isn't ingraph:getreturnsNonefor a pattern with no bucket andunwrap_or_default()turns that into an empty vector. - A word is its own neighbor. Every word sits in its own buckets, so it shows up when it is expanded. It already has an entry in
min_dist, so the visited check skips it. - Indexing the map.
min_dist[&word]would panic for a missing key. Every word taken from the queue was inserted first, so it is safe.
Complexity
Let N be the number of words and L their length.
Time: O(N · L²). Building the graph makes N · L patterns, and each costs O(L) to build and hash. The BFS expands each word once, with L pattern lookups of cost O(L) each. The buckets hold at most 26 words, so copying them adds only a constant factor.
Space: O(N · L²). The graph has up to N · L patterns, each of length L, and it stores N · L word copies of length L. The queue and min_dist add O(N · L).
Edge cases and common mistakes
end_wordnot in the list. It never appears in a bucket, so the queue empties and the function returns 0.begin_wordnot in the list. It only needs to be expandable, and its patterns still find the list's words. Withbegin_word = "hot",end_word = "dot"andwords = ["dot"]the result is 2.- Distance base. The seed distance is 1 because the chain
begin_wordalone has one word. Seeding with 0 shifts every answer down by one. - Different lengths. A pattern only matches words of the same length. The lesson guarantees equal lengths.
- Forgetting the visited check. Words in the same bucket are neighbors of each other, so without the
min_disttest the BFS would push them back and forth forever. - Moving the vector. Writing
for word in wordsinstead offor word in &wordsconsumes the list and hands out owned strings, so the callSelf::get_star_word(word, i)no longer matches the helper's&strparameter. Borrowing keeps the vector intact and yields&Stringvalues.
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 = ["hot", "dot"]give 2.begin_word = "ab",end_word = "cd"andwords = ["ad", "cd"]give 3.
