Problem overview
The function ladderLength receives a start word, beginWord, a target word, endWord, and a slice of allowed words, words. A transformation changes exactly one letter at a time, and every word you step onto must be in words. The function returns the number of words in the shortest chain from beginWord to endWord, counting both ends, or 0 if no chain exists.
With beginWord = "hit", endWord = "cog" and words = ["hot","dot","dog","lot","log","cog"], one shortest chain is hit -> hot -> dot -> dog -> cog. It holds five words, so the answer is 5. If "cog" is removed from the list, the target can never be reached and the answer is 0.
Approach: treat words as a graph and search level by level
Think of every word as a node, with an edge between two words that differ in exactly one position. The task is then "find the shortest path in an unweighted graph", and the tool for that is breadth-first search (BFS). BFS visits all words one step from the start, then all words two steps away, and so on. The first time it reaches the target, no shorter chain can exist.
The graph is never built explicitly. Whenever the search takes a word out of the queue, it scans the whole list and tests each candidate with a small helper that counts differing positions. A candidate is a neighbour when that count is exactly 1.
This is the simplest version, and also the slowest one. Each dequeued word is compared with all N words in the list, and each comparison looks at up to L letters. Other lessons on this problem generate neighbours differently to avoid that scan. Here the goal is to get BFS right first.
Step by step
- Create the queue as a
[]stringthat already holdsbeginWord. A slice works as a queue: new words go on the back and the next word comes from the front. - Create the distance map,
minDistance, from word to chain length, withbeginWordat 1 because the chain counts the start word. A word with an entry has been reached already, so the same map doubles as the visited set. - Loop while the queue has words. Go has no
while, so this is aforwith only a condition:len(queue) > 0. - Take the front word into
wordand drop it from the queue by re-slicing from index 1. If it equalsendWord,break. Its distance is already stored, and BFS took it out in order of distance, so that value is the shortest. - Try every candidate. Loop over
wordswithrange, discarding the index with_. - Skip anything that isn't one change away. A count of 0 means the very same word, and 2 or more means more than one letter would change. Only a count of exactly 1 is a legal move.
- Skip words already reached. If
nextWordis inminDistance, an earlier path got there in at most as many steps, so a new path is no improvement. - Record and enqueue a new word: its distance is
minDistance[word] + 1, and it joins the back of the queue. - Return
minDistance[endWord]after the loop. If the target was never reached there is no entry, and Go gives the zero value, 0, which is exactly the "no sequence" answer. - Write the helper
numOfChanges: setdifferencesto 0, loop over every index offirst, add one wheneverfirst[i]andsecond[i]differ, and return the total.
The solution in Go
func ladderLength(beginWord, endWord string, words []string) int {
queue := []string{beginWord}
minDistance := map[string]int{beginWord: 1}
for len(queue) > 0 {
word := queue[0]
queue = queue[1:]
if word == endWord {
break
}
for _, nextWord := range words {
if numOfChanges(word, nextWord) != 1 {
continue
}
if _, exists := minDistance[nextWord]; exists {
continue
}
minDistance[nextWord] = minDistance[word] + 1
queue = append(queue, nextWord)
}
}
return minDistance[endWord]
}
func numOfChanges(first, second string) int {
differences := 0
for i := 0; i < len(first); i++ {
if first[i] != second[i] {
differences++
}
}
return differences
}
The Go details worth knowing:
- A slice as a queue.
queue = queue[1:]copies nothing. It makes the slice start one element later in the same backing array. That is cheap and fine for a search this size. appendreturns the slice. It may have to move the elements into a bigger array, so the result must be assigned back:queue = append(queue, nextWord). Callingappendand ignoring its result doesn't compile.- Missing map keys. Reading a key that isn't there gives the zero value, so
minDistance[endWord]is 0 for an unreached word. That is convenient at the very end, but inside the loop it would be a trap: 0 can't tell "not seen" from "seen". The comma-ok form_, exists := minDistance[nextWord]answers that question directly. The variable declared in anifheader exists only inside thatif. - Indexing a string gives a byte.
first[i] != second[i]compares two bytes. For lowercase English letters one byte is one letter, which is what this problem guarantees. - Helpers can come after their use. Package-level functions can be declared in any order, so
numOfChangessits belowladderLengthwithout any forward declaration. - Shared parameter types. In
(first, second string)both parameters are strings. The same shortcut is inladderLength's first line. - Unused names are errors. Writing
for i, nextWord := range wordsand never usingifails with "i declared and not used". That is why the index is replaced with_.
Complexity
Let N be the number of words and L their length.
Time: O(N² * L). A word is enqueued at most once, because it gets a distance the first time it is found and is skipped afterwards. Each dequeued word triggers a scan of all N candidates, and each candidate costs up to L byte comparisons in numOfChanges. That gives N * N * L.
Space: O(N * L). The map holds up to N + 1 words and the queue never holds more than that. Strings in the map and queue share the list's own bytes, but counting them as length L each is the safe bound.
Edge cases and common mistakes
- The target is missing from the list. The search never reaches it and the function returns 0, as in the second example.
- The start word is allowed to be absent from the list. It is only a starting point. If it does appear in the list,
numOfChangesreturns 0 against itself and the word is skipped. - One step away.
"hit"to"hot"withwords = ["hot"]gives 2, because the chain is two words long. A common mistake is to return the number of changes, 1, instead of the number of words. - Starting the distance at 0. The statement counts both ends, so the first word has distance 1.
- Checking visited after enqueueing, or not at all. Without the
existscheck, a word can be enqueued many times and the search can loop forever between two neighbours. - Using
!= 1as< 2. A count of 0 is the same word, which must not count as a move. - Expecting the first path found to be shortest in a depth-first search. It isn't. BFS gets this right only because it processes words in order of distance.
Testing
"hit","cog",["hot","dot","dog","lot","log","cog"]gives5."hit","cog",["hot","dot","dog","lot","log"]gives0."hit","hot",["hot"]gives2."a","c",["a","b","c"]gives2, since single letters differ in one position.