Problem overview
The function ladderLength takes beginWord, endWord and a slice words. It changes one letter at a time, and each new word must be in words. It returns the number of words in the shortest chain from beginWord to endWord, with both ends counted, or 0 when there is no chain.
For "hit" to "cog" with ["hot","dot","dog","lot","log","cog"], the shortest chain is hit, hot, dot, dog, cog, so the answer is 5. Without "cog" in the list the answer is 0.
Approach: generate neighbours instead of searching for them
Shortest path in an unweighted graph means breadth-first search (BFS). Words are nodes, and two words are connected when they differ in one letter. The only question is how to find a word's neighbours.
One way is to compare the word with every entry in the list. That costs one comparison per list entry for every word taken from the queue, so it grows with the size of the list. This lesson turns the problem around. A word with L letters has only 26 * L possible one-letter variants, no matter how long the list is. So the code produces each variant and asks whether it is in the list. For that question to be fast, the list is first copied into a set, where a membership test is a single lookup on average.
The rest is a standard BFS: a queue, and a map of distances that also records which words were already reached.
Step by step
- Build a set of words. Go has no set type, so use a
map[string]struct{}made withmake. Only the keys matter, and the empty struct takes no memory for the values. A map declared withvaralone isniland can't be written to. - Fill the set by ranging over
wordsand storingstruct{}{}under each word. - Create the queue as a slice holding
beginWord. - Create
minDistance, a map from word to chain length, withbeginWordat 1. It doubles as the visited set. - Loop while the queue isn't empty, with a condition-only
for. - Dequeue the front word and re-slice the queue to drop it.
- Stop at the target. When the word equals
endWord, return its stored distance. BFS dequeues words in order of distance, so it is the shortest. - Loop over each position of the word, then over each letter from
'a'to'z'. The letter variable starts asbyte('a')so it is abyte, the type the next step stores it into. - Build the candidate. Strings can't be modified, so copy the word into a
[]byte, replace the byte at the current position, and convert the result back to a string,nextWord. - Filter the candidate. Skip it if it isn't in
wordSet, then skip it if it's already inminDistance. Both checks use the comma-ok lookup. - Record and enqueue. Set its distance to the current word's distance plus one and append it to the queue.
- Return 0 after the loop. If the queue runs out without producing
endWord, no chain exists.
The solution in Go
func ladderLength(beginWord, endWord string, words []string) int {
wordSet := make(map[string]struct{})
for _, word := range words {
wordSet[word] = struct{}{}
}
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++ {
for character := byte('a'); character <= 'z'; character++ {
chars := []byte(word)
chars[i] = character
nextWord := string(chars)
if _, exists := wordSet[nextWord]; !exists {
continue
}
if _, exists := minDistance[nextWord]; exists {
continue
}
minDistance[nextWord] = minDistance[word] + 1
queue = append(queue, nextWord)
}
}
}
return 0
}
The Go details worth knowing:
struct{}andstruct{}{}. The first is the empty struct type and the second is its only value. Amap[string]boolwould also work as a set, but the empty struct makes it clear that the values carry no information.- Bytes versus runes. A character literal such as
'a'is aruneby default, which is an alias forint32. Slice elements of[]bytearebytevalues, and Go does not convert between them silently. Writingfor character := 'a'; ...and thenchars[i] = characterfails to compile with "cannot use character (variable of type rune) as byte value in assignment". Starting frombyte('a')fixes the type. The comparisoncharacter <= 'z'still works because the untyped constant'z'adapts tobyte. - Copying before editing.
[]byte(word)allocates a fresh copy each time it runs. Changingcharsnever changesword, because strings are immutable and the conversion copies. That is why the copy sits inside the letter loop: each candidate starts from the original word. lencounts bytes. For a string it returns the length in bytes, which is the number of letters for lowercase English words.- Scope of
exists. Eachifheader declares its ownexists, so both can use the same name. - Nil map writes panic. Reading from a
nilmap is fine and gives zero values, but storing a key into one stops the program with "assignment to entry in nil map".makeor a literal avoids that. - Returning from inside the loop. The function can return the moment the target is dequeued, so no
breakis needed, and the finalreturn 0covers the case where the loop ends on its own. Go requires a function with a result to end with a return statement.
Complexity
Let N be the number of words and L the word length.
Time: O(N * L * 26 * L), which is O(N * L²). Each word is enqueued at most once. For each dequeued word there are L positions and 26 letters, so 26 * L candidates. Building a candidate copies L bytes, and hashing it for the set lookup also reads L bytes. Compared with scanning the whole list for each word, the work no longer depends on N per word, only on the alphabet and the word length. This is much better when the list is long and the words are short.
Space: O(N * L). The set, the distance map and the queue each hold at most about N words of length L.
Edge cases and common mistakes
- The target isn't in the list. It is never generated as a valid candidate, so the function returns 0.
- The start word isn't in the list. That's fine: it starts in the queue and in
minDistance, and only the later words are checked againstwordSet. - Generating the word itself. When the letter equals the one already at position
i, the candidate is the original word. It is either not in the set or already inminDistance, so the second filter discards it. - Forgetting the visited check. Without it a word can be queued again from every neighbour, and the search can run in circles.
- Counting changes instead of words.
"hit"to"hot"with["hot"]returns 2, not 1. - Sharing one byte slice. If
charswere created once, outside the loops, a letter written at position 0 would stay there while position 1 is tried, and the candidates would differ from the word in two places. Buildingcharsfromwordinside the letter loop keeps every candidate one change away.
Testing
"hit","cog",["hot","dot","dog","lot","log","cog"]gives5."hit","cog",["hot","dot","dog","lot","log"]gives0."hit","hot",["hot"]gives2.