Problem overview
The function ladderLength receives beginWord, endWord and a slice words. Each move changes exactly one letter, and every word you land on must be in words. It returns the number of words in the shortest chain from beginWord to endWord, counting both, or 0 if there is no chain.
For "hit" to "cog" with ["hot","dot","dog","lot","log","cog"] the answer is 5, through hit, hot, dot, dog, cog. If "cog" is not in the list, the answer is 0.
Approach: group words by wildcard pattern
Breadth-first search (BFS) finds the shortest path, but it needs a quick way to list a word's neighbours. Comparing against the whole list is slow, and trying all 26 letters at every position builds many candidates that mostly aren't words at all.
This lesson uses a different observation. Replace one letter of a word with * and you get a pattern: hot gives *ot, h*t and ho*. Two words differ in exactly one position when they share a pattern at that position. So hot, dot and lot all appear under *ot, and that bucket is precisely the set of words one letter away from each of them in the first position.
The plan has two phases. First, one pass over the list builds a map from each pattern to the words that match it. Then BFS runs as usual, but to find the neighbours of a word it builds that word's patterns and reads the matching buckets. No candidate that isn't in the list is ever generated.
Step by step
- Declare
graphas amap[string][]string, from pattern to words, created withmake. - Loop over the words, and for each word loop over every position
i. - Build the pattern with a helper,
getStarWord(word, i). It is written at the end, and Go lets code call a function declared further down the file. - Add the word to its bucket:
graph[starWord] = append(graph[starWord], word). No check for a missing key is needed. A missing key reads as anilslice, andappendaccepts anilslice and returns a new one. - Set up the BFS as in any shortest-path search: a queue holding
beginWord, and a mapminDistancewithbeginWordat 1. The map also records which words are already reached. - Loop while the queue has words, take the front word and re-slice the queue.
- Stop at the target. If the word is
endWord, return its distance. Words leave the queue in order of distance, so the first arrival is the shortest. - For each position of the word, build its pattern with the same helper.
- Walk the bucket
graph[starWord]. Each word in it differs from the current word only at that position. If the pattern isn't in the map, the lookup gives anilslice and the loop runs zero times. - Visit each unseen neighbour once: if it has no entry in
minDistance, give it the distanceminDistance[word] + 1and append it to the queue. - Return 0 after the loop because the queue emptied without reaching the target.
- Write
getStarWord. It returns the part ofwordbefore indexi, then"*", then the part after indexi.
The solution in Go
func ladderLength(beginWord, endWord string, words []string) int {
graph := make(map[string][]string)
for _, word := range words {
for i := 0; i < len(word); i++ {
starWord := getStarWord(word, i)
graph[starWord] = append(graph[starWord], word)
}
}
queue := []string{beginWord}
minDistance := map[string]int{beginWord: 1}
for len(queue) > 0 {
word := queue[0]
queue = queue[1:]
if word == endWord {
return minDistance[word]
}
for i := 0; i < len(word); i++ {
starWord := getStarWord(word, i)
for _, nextWord := range graph[starWord] {
if _, exists := minDistance[nextWord]; !exists {
minDistance[nextWord] = minDistance[word] + 1
queue = append(queue, nextWord)
}
}
}
}
return 0
}
func getStarWord(word string, i int) string {
return word[:i] + "*" + word[i+1:]
}
The Go details worth knowing:
- Slicing strings.
word[:i]is the substring before indexiandword[i+1:]is the substring after it. Indexiitself is left out of both, which is how the letter disappears. For"hot",getStarWord("hot", 1)is"h*t". Slicing is by byte, which suits lowercase English letters. - Building with
+. Strings are immutable, so each+creates a new string. That is fine for three short pieces. - A
nilslice is a usable empty slice.len,rangeandappendall work on it. This is what lets the code skip the "is the key there?" check twice, in the graph-building loop and in the search. - The pattern buckets include the word itself.
hotis in all three of its own buckets. When the search reads them, it meetshot, butminDistancealready has an entry for it (it was just dequeued), so it is skipped. - The start word needn't be in the list.
"hit"adds nothing to the graph, but the search still builds its patterns*it,h*tandhi*and reads their buckets. Onlyh*tholds a word,hot. - Two scopes for
starWord. The name is declared in the first loop and again in the search. Each loop body is its own scope, so there is no clash.
Complexity
Let N be the number of words and L their length.
Time to build the graph: O(N * L²). There are N * L pattern insertions, and each one builds a string of length L and hashes it.
Time for the search. Every word is dequeued at most once. For each one the code builds L patterns, at O(L) each, and walks the matching buckets. When the buckets are small, this is about O(N * L²) in total, the same as the build. A bucket is walked once for every dequeued word that matches its pattern, so a bucket with k words costs up to k² in the worst case, when most words share a pattern. In ordinary word lists the buckets stay small.
Space: O(N * L²). Each word is stored in L buckets, and each of the N * L pattern keys is a string of length L. The word strings in the buckets share memory with the list, so the keys dominate.
Edge cases and common mistakes
- Target missing from the list. It never appears in any bucket, so it's never reached, and the result is 0.
- Same pattern, different positions. Patterns from different positions can't collide:
*otandh*tdiffer in where the star is, so they are different keys. - Counting the chain length wrongly.
"hit"to"hot"with["hot"]returns 2, since both words count. - Skipping the visited check. Words are in several buckets and neighbours point back to each other, so without the
minDistancecheck the queue would grow without end. - Ignoring the assignment of
append. Writingappend(graph[starWord], word)on its own line doesn't compile, because the result is unused. The result has to be stored back into the map.
Testing
"hit","cog",["hot","dot","dog","lot","log","cog"]gives5."hit","cog",["hot","dot","dog","lot","log"]gives0."hit","hot",["hot"]gives2.