https://leetcode.com/problems/word-ladder

word-ladder.go

const inf = (1 << 31) - 1

type pair struct {
    id int
    level int
}

func ladderLength(beginWord string, endWord string, wordList []string) int {
    graph := make(map[string][]int)
    
    for _, word := range append(wordList, beginWord) {
        for i, candidate := range wordList {
            if word != candidate && canBeTransformed(word, candidate) {
                graph[word] = append(graph[word], i)
            }
        }
    }
    
    length := findMinPathLength(graph, wordList, beginWord, endWord)
    
    if length == inf {
        return 0
    }
    
    return length
}

func findMinPathLength(graph map[string][]int, wordList []string, from, to string) int {
    length := inf
    
    for _, child := range graph[from] {
        queue := []pair{{child, 2}}
        visited := make([]bool, len(wordList))
        
        for len(queue) > 0 {
            p := queue[0]
            queue = queue[1:]
            node := wordList[p.id]
            visited[p.id] = true
            
            if node == to {
                length = min(length, p.level)
                continue
            }
            
            for _, neighbour := range graph[node] {
                if !visited[neighbour] {
                    queue = append(queue, pair{
                        neighbour,
                        p.level + 1,
                    })
                }
            }
        }
    }
    
    return length
}

func canBeTransformed(from, to string) bool {
    diff := 0
    
    for i := 0; i < len(from) && diff <= 1; i++ {
        if from[i] != to[i] {
            diff++
        }
    }
    
    return diff <= 1
}

func min(a, b int) int {
    if a < b {
        return a
    }
    
    return b
}