Problem overview
The function ladderLength receives beginWord, endWord and a slice words. It returns the number of words in the shortest sequence that starts at beginWord, ends at endWord, and changes exactly one letter at each step. Every word after the first must be in words. If no such sequence exists, it returns 0. All words have the same length and contain lowercase letters only.
With beginWord = "hit", endWord = "cog" and words = ["hot", "dot", "dog", "lot", "log", "cog"], one shortest sequence is hit -> hot -> dot -> dog -> cog, so the answer is 5. The length counts words, not steps. If "cog" is removed from the list, no sequence can end at it, and the answer is 0.
Approach: a graph of words, searched from both ends
Words are the nodes of a graph, and two words are connected when they differ in exactly one letter. The shortest sequence is a shortest path, and breadth-first search (BFS) finds shortest paths in graphs whose edges all have the same cost.
Two ideas make this version efficient.
Patterns instead of pairwise comparison
Comparing every pair of words to find neighbors is slow. Instead, replace one letter of a word with * to get a pattern: hot gives *ot, h*t and ho*. Two words differ in exactly one letter if and only if they share a pattern. So a map from each pattern to the list of words that match it does the job. The neighbors of a word are the words in the lists of its patterns.
Searching from both ends
A plain BFS from beginWord grows its frontier wider at every level. Running two searches, one from beginWord and one from endWord, and stopping when they meet, covers much less ground, because each only has to go about halfway. This lesson does that, and always expands the side whose current level has fewer words, which is the cheaper one to grow.
Each side keeps a queue and a map from word to distance, counting the words from its own start, so the start itself has distance 1. When one side finds a neighbor that the other side has already reached, the two searches have met. The length of the whole sequence is the distance of the current word plus the distance of that neighbor, because the two parts together cover every word once.
To be sure the first meeting is the shortest, the code expands a whole level at a time. If it expanded one word at a time, a meeting could happen through a longer sequence while a shorter one was still waiting in a queue.
Step by step
- Check that
endWordis inwords. Start withfound := falseand loop overwordswithrange. Go slices have no built-in "contains". - Stop at the match. When
w == endWord, setfound = trueandbreak. - Give up if it's missing. If
!found, return 0. No sequence can end at a word that isn't in the list. - Write
getStarWord(word, i). It returnsword[:i] + "*" + word[i+1:]: the part before indexi, a star, and the part after it. - Write
buildGraph(words). It creates the map withmake(map[string][]string). - Loop over every word and every position. Compute
starWordand append the word tograph[starWord]. A missing key reads as a nil slice andappendaccepts a nil slice, so no special case is needed for a new pattern. - Return the graph, and in
ladderLengthstore it ingraph. - Set up both searches. Two queues,
beginQueueandendQueue, each start with their own word. Two maps,beginMinDistandendMinDist, record 1 for those words. Each map's keys are also the words that side has visited. - Declare
result := 0to receive the outcome of each expansion. - Loop while neither queue is empty. Once one side runs out of words, the searches can never meet.
- Write
processLevel. It takes the graph, a pointer to the queue to expand and two distance maps: the expanding side's and the other side's. - Fix the level's size as
levelSize := len(*queue)and loop exactly that many times. Words added during this call belong to the next level. - Pop the front word.
word := (*queue)[0], then*queue = (*queue)[1:]. - Visit its neighbors. For each position, compute the pattern and range over the words stored under it in the graph.
- Detect the meeting. If
otherMinDisthasnextWord, returnminDist[word] + otherMinDist[nextWord]. - Visit new words only. If
minDistdoesn't havenextWord, set its distance tominDist[word] + 1and append it to the queue. - Return 0 when the level ends without a meeting. A real sequence has at least two words, so 0 can't be mistaken for an answer.
- Choose the side. In
ladderLength, iflen(beginQueue) <= len(endQueue), expand the begin side. Otherwise expand the end side with the roles swapped. - Return when they meet. If
result != 0, return it. After the loop, return 0.
The solution in Go
func getStarWord(word string, i int) string {
return word[:i] + "*" + word[i+1:]
}
func buildGraph(words []string) map[string][]string {
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)
}
}
return graph
}
func processLevel(graph map[string][]string, queue *[]string, minDist map[string]int, otherMinDist map[string]int) int {
levelSize := len(*queue)
for k := 0; k < levelSize; k++ {
word := (*queue)[0]
*queue = (*queue)[1:]
for i := 0; i < len(word); i++ {
starWord := getStarWord(word, i)
for _, nextWord := range graph[starWord] {
if _, ok := otherMinDist[nextWord]; ok {
return minDist[word] + otherMinDist[nextWord]
}
if _, ok := minDist[nextWord]; !ok {
minDist[nextWord] = minDist[word] + 1
*queue = append(*queue, nextWord)
}
}
}
}
return 0
}
func ladderLength(beginWord, endWord string, words []string) int {
found := false
for _, w := range words {
if w == endWord {
found = true
break
}
}
if !found {
return 0
}
graph := buildGraph(words)
beginQueue := []string{}
endQueue := []string{}
beginMinDist := map[string]int{}
endMinDist := map[string]int{}
beginQueue = append(beginQueue, beginWord)
endQueue = append(endQueue, endWord)
beginMinDist[beginWord] = 1
endMinDist[endWord] = 1
result := 0
for len(beginQueue) > 0 && len(endQueue) > 0 {
if len(beginQueue) <= len(endQueue) {
result = processLevel(graph, &beginQueue, beginMinDist, endMinDist)
} else {
result = processLevel(graph, &endQueue, endMinDist, beginMinDist)
}
if result != 0 {
return result
}
}
return 0
}
The Go details worth knowing:
- Slicing strings.
word[:i]ends before indexiandword[i+1:]starts after it. Indexes are byte positions, which is fine for lowercase letters. Strings are immutable, so+builds a new string. - Appending to a missing map key. Reading a key that isn't in a map gives the zero value, which for a slice is
nil, andappendworks onnil:
graph := make(map[string][]string)
graph["*ot"] = append(graph["*ot"], "hot")
graph["*ot"] = append(graph["*ot"], "dot")
fmt.Println(graph["*ot"], len(graph["h*t"])) // [hot dot] 0
- The comma-ok lookup.
_, ok := m[key]tells whether a key is present, which a plain lookup can't, because it returns 0 for a missingint. Writing it asif _, ok := ...; ok { ... }keepsokinside thatif. - Ranging over a missing pattern.
graph[starWord]isnilfor an unknown pattern, and arangeovernilruns zero times. - Why the queue is a pointer but the maps are not. Pushing and popping change the slice's length, so
processLevelreceives*[]stringand works through*queue. A map value already refers to the shared table, so assignments inside the function are seen by the caller. The call passes&beginQueueto hand over the address. (*queue)[0]. Indexing binds tighter than*, so the parentheses dereference first.- Popping with
[1:]. It moves the slice's start forward and costsO(1). The skipped element is not reused untilappendmoves the data to a new array.
Complexity
Let N be the number of words and L their length.
Building the graph: O(N * L²). Each word yields L patterns, and building each pattern copies L characters. The map holds N * L keys of length L, so it takes O(N * L²) space.
Search: at most O(N² * L), usually far less. Each side expands a word at most once, and an expansion looks at L patterns. A pattern's list can hold many words, so in the worst case an expansion looks at up to N words per pattern, which gives the bound. In practice the lists are short, and searching from both ends keeps the frontiers small.
Extra space for the search: the two queues and the two distance maps hold at most N words each, so O(N) on top of the graph.
Edge cases and common mistakes
endWordnot in the list. The function returns 0 at once, before building anything. The second example in the statement is this case.beginWordnot in the list. That is allowed. The graph holds only the list's words, so the search from the end side can never step ontobeginWord. Only the begin side's first expansion connects it to the rest, which is why the begin side must go first on a tie.- The tie-break. With
beginWord = "hot",endWord = "dot"andwords = ["dot"], the answer is 2. If a tie expanded the end side first, it would find nothing, run out of words and return 0. That is why the condition is<=, not<. - Expanding one word at a time instead of a whole level can return a longer sequence than the shortest one.
levelSizefixes the number of words before the loop. - Adding the two distances correctly. The distances count words from each end, and the meeting word is counted on one side only:
minDist[word]ends atwordandotherMinDist[nextWord]starts atnextWord. On the example, the begin side reachesdotwith distance 3 and the end side reachesdogwith distance 2, so the answer is 5. Adding 1 for the edge between them would give 6. - Revisiting words. Each side marks a word visited when it first reaches it. Without that check, the queues would fill with duplicates, or loop forever.
Testing
"hit","cog",["hot", "dot", "dog", "lot", "log", "cog"]gives 5."hit","cog",["hot", "dot", "dog", "lot", "log"]gives 0."hot","dot",["dot"]gives 2.
