Golang | Leetcode Golang题解之第127题单词接龙

题目：

题解：

func ladderLength(beginWord string, endWord string, wordList []string) int {wordId := map[string]int{}graph := [][]int{}addWord := func(word string) int {id, has := wordId[word]if !has {id = len(wordId)wordId[word] = idgraph = append(graph, []int{})}return id}addEdge := func(word string) int {id1 := addWord(word)s := []byte(word)for i, b := range s {s[i] = '*'id2 := addWord(string(s))graph[id1] = append(graph[id1], id2)graph[id2] = append(graph[id2], id1)s[i] = b}return id1}for _, word := range wordList {addEdge(word)}beginId := addEdge(beginWord)endId, has := wordId[endWord]if !has {return 0}const inf int = math.MaxInt64distBegin := make([]int, len(wordId))for i := range distBegin {distBegin[i] = inf}distBegin[beginId] = 0queueBegin := []int{beginId}distEnd := make([]int, len(wordId))for i := range distEnd {distEnd[i] = inf}distEnd[endId] = 0queueEnd := []int{endId}for len(queueBegin) > 0 && len(queueEnd) > 0 {q := queueBeginqueueBegin = nilfor _, v := range q {if distEnd[v] < inf {return (distBegin[v]+distEnd[v])/2 + 1}for _, w := range graph[v] {if distBegin[w] == inf {distBegin[w] = distBegin[v] + 1queueBegin = append(queueBegin, w)}}}q = queueEndqueueEnd = nilfor _, v := range q {if distBegin[v] < inf {return (distBegin[v]+distEnd[v])/2 + 1}for _, w := range graph[v] {if distEnd[w] == inf {distEnd[w] = distEnd[v] + 1queueEnd = append(queueEnd, w)}}}}return 0
}