package main

// begin & end are non-empty and not the same
func ladderLength(beginWord string, endWord string, wordList []string) int {
	wordCnt := len(wordList)
	if wordCnt == 0 {
		return 0
	}
	target := -1
	for i := 0; i < wordCnt; i++ {
		if wordList[i] == endWord {
			target = i
			break
		}
	}
	if target == -1 {
		return 0
	}
	newList := append(wordList, beginWord)
	distance := make([]int, wordCnt+1)
	distance[wordCnt] = 1 // Initial ladder length: 1
	isMin := make([]bool, wordCnt+1)
	queue := make([]int, 0)
	queue = append(queue, wordCnt)
	for len(queue) != 0 { // Dijkstra method
		newQueue := make([]int, 0)
		for len(queue) != 0 {
			idx := queue[0]
			queue = queue[1:] // Dequeue
			for i := 0; i < wordCnt; i++ {
				if !isMin[i] {
					if isConvertible(newList[idx], newList[i]) &&
						(distance[i] == 0 || distance[idx] < distance[i]) {
						distance[i] = distance[idx] + 1
					}
					if len(queue) == 0 && distance[i] != 0 {
						newQueue = append(newQueue, i)
						isMin[i] = true
					}
				}
			}
		}
		queue = newQueue
	}
	return distance[target]
}

func isConvertible(src, dst string) bool {
	diff := 0
	for i := 0; i < len(src); i++ {
		if src[i] != dst[i] {
			diff++
		}
	}
	return diff == 1
}

// func main() {
// 	wordList := []string{"hot", "dot", "dog", "lot", "log", "cog"}
// 	println(ladderLength("dog", "but", wordList))
// 	println(ladderLength("hit", "cog", wordList))
// }