package main

func findLadders(beginWord string, endWord string, wordList []string) (ladders [][]string) {
	endIdx, listLen := -1, len(wordList)
	for i := 0; i < listLen; i++ {
		if endWord == wordList[i] {
			endIdx = i
			break
		}
	}
	if endIdx == -1 {
		return
	} // Find end word in word list, if not found, return false
	adj := make([][]int, listLen)
	for i := 0; i < listLen; i++ {
		for j := i + 1; j < listLen; j++ {
			if isConvertible(wordList[i], wordList[j]) {
				adj[i] = append(adj[i], j) // Dont need to init each row of adj if use append
				adj[j] = append(adj[j], i)
			}
		}
	} // Create adj matrix
	visited := make([]bool, listLen)
	closest := make([]int, 0)
	distance := make([]int, listLen) // Distance from begin to word i
	prev := make([][]int, listLen)   // List of prev point
	for i := 0; i < listLen; i++ {
		prev[i] = make([]int, 0)
		if isConvertible(beginWord, wordList[i]) {
			prev[i] = append(prev[i], -1) // -1 means begin word
			closest = append(closest, i)
			distance[i] = 1
			visited[i] = true
		}
	} // Init closest array
	for distance[endIdx] == 0 && len(closest) != 0 {
		newClosest := make([]int, 0)
		for _, c := range closest {
			for _, i := range adj[c] {
				if !visited[i] {
					if distance[i] == 0 {
						distance[i] = distance[c] + 1
						newClosest = append(newClosest, i)
					}
					prev[i] = append(prev[i], c)
				}
			}
		}
		for i := range newClosest {
			visited[newClosest[i]] = true
		}
		closest = newClosest
	}
	var getLadders func(int, []string) // Get ladders from prev path
	getLadders = func(idx int, ladder []string) {
		var newLadder []string
		if idx == -1 {
			newLadder = []string{beginWord}
			newLadder = append(newLadder, ladder...)
			ladders = append(ladders, newLadder)
			return
		}
		newLadder = []string{wordList[idx]}
		newLadder = append(newLadder, ladder...)
		for i := range prev[idx] {
			getLadders(prev[idx][i], newLadder)
		}
	}
	getLadders(endIdx, []string{})
	return
}

func isConvertible(a, b string) bool {
	diff := 0
	for i := range a {
		if a[i] != b[i] {
			diff++
		}
		if diff > 1 {
			return false
		}
	}
	return diff == 1
}

// func main() {
// 	fmt.Println(findLadders(
// 		"hit",
// 		"cog",
// 		[]string{"hot", "dot", "dog", "lot", "log", "cog"}))
// 	fmt.Println(findLadders(
// 		"hit",
// 		"cog",
// 		[]string{"hot", "dot", "dog", "lot", "log"}))
// 	fmt.Println(findLadders(
// 		"hot",
// 		"dog",
// 		[]string{"hot", "dog", "dot"}))
// }