Word Ladder

LeetCode 127 · View on LeetCode

BFS on an implicit graph. Each word is a node. Two words are neighbors if they differ by one letter. Try all 26 replacements at each position.

package main

import "fmt"

func ladderLength(beginWord, endWord string, wordList []string) int {
	wordSet := map[string]bool{}
	for _, w := range wordList {
		wordSet[w] = true
	}
	if !wordSet[endWord] {
		return 0
	}

	queue := []string{beginWord}
	visited := map[string]bool{beginWord: true}
	steps := 1

	for len(queue) > 0 {
		size := len(queue)
		for i := 0; i < size; i++ {
			word := queue[0]
			queue = queue[1:]
			if word == endWord {
				return steps
			}
			buf := []byte(word)
			for j := 0; j < len(buf); j++ {
				orig := buf[j]
				for ch := byte('a'); ch <= 'z'; ch++ {
					if ch == orig {
						continue
					}
					buf[j] = ch
					next := string(buf)
					if wordSet[next] && !visited[next] {
						visited[next] = true
						queue = append(queue, next)
					}
				}
				buf[j] = orig
			}
		}
		steps++
	}
	return 0
}

func main() {
	wordList := []string{"hot", "dot", "dog", "lot", "log", "cog"}
	fmt.Println(ladderLength("hit", "cog", wordList)) // 5 (hit->hot->dot->dog->cog)
}