Word Ladder

Hard

The problem

Start from beginWord and change exactly one letter at a time to reach endWord. Every word you land on (including endWord) must be in wordList. Return the number of words in the shortest such sequence, counting beginWord and endWord, or 0 if it is impossible.

Example 1
Input: beginWord = "hit", endWord = "cog", wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
Output: 5
hit, hot, dot, dog, cog is 5 words long.
Example 2
Input: beginWord = "hit", endWord = "cog", wordList = ["hot", "dot", "dog", "lot", "log"]
Output: 0
"cog" is not in the list, so it cannot be reached.

Limits

All words have the same length, 1 to 10 lowercase letters
1 ≤ len(wordList) ≤ 5,000
beginWord does not have to be in wordList
beginWord and endWord are different

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Words are nodes; two words are connected if they differ by one letter. You want the fewest hops.

The idea

BFS from beginWord, generating neighbours by changing one letter (or via wildcard buckets like h*t) that exist in the word set; the layer count is the answer.

Target: O(N · L²) time

Go function shape

func ladderLength(beginWord string, endWord string, wordList []string) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// LadderLength: words are nodes, and two words are connected when they differ by one letter.
// BFS from beginWord counts the fewest words in a transformation sequence. Neighbours are found by trying all
// 26 letters in each position and keeping those in the word list; each word is removed once seen.
func LadderLength(beginWord, endWord string, wordList []string) int {
	words := make(map[string]bool, len(wordList))
	for _, w := range wordList {
		words[w] = true
	}
	if !words[endWord] {
		return 0
	}
	queue := []string{beginWord}
	delete(words, beginWord)
	for steps := 1; len(queue) > 0; steps++ {
		for size := len(queue); size > 0; size-- {
			cur := queue[0]
			queue = queue[1:]
			if cur == endWord {
				return steps
			}
			b := []byte(cur)
			for i := range b {
				orig := b[i]
				for ch := byte('a'); ch <= 'z'; ch++ {
					b[i] = ch
					if next := string(b); words[next] {
						delete(words, next) // visited
						queue = append(queue, next)
					}
				}
				b[i] = orig
			}
		}
	}
	return 0
}

Read the lesson: Graphs: BFS / DFS / Topological Sort