字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> … -> sk：
每一对相邻的单词只差一个字母。
对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
sk == endWord
给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。
示例 1：
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。示例 2：
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中，所以无法进行转换。提示：
- 1 <= beginWord.length <= 10
- endWord.length == beginWord.length
- 1 <= wordList.length <= 5000
- wordList[i].length == beginWord.length
- beginWord、endWord 和 wordList[i] 由小写英文字母组成
- beginWord != endWord
- wordList 中的所有字符串 互不相同
解题：
// 对昨天的结果取长度就好
func backtrack(from map[string][]string, path []string, beginWord, cur string, res [][]string) [][]string {
if cur == beginWord {
res = append(res, path)
return res
}
for _, v := range from[cur] {
path = append([]string{v}, path...)
res = backtrack(from, path, beginWord, v, res)
path = path[1:]
}
return res
}
func ladderLength(beginWord string, endWord string, wordList []string) int {
var res [][]string
// 因为需要快速判断扩展出的单词是否在 wordList 里，因此需要将 wordList 存入哈希表，这里命名为「字典」
data := make(map[string]string)
for i := range wordList {
data[wordList[i]] = wordList[i]
}
// 特殊用例判断
if _, ok := data[endWord]; !ok {
return 0
}
delete(data, beginWord)
// 第 1 步：广度优先搜索建图
// 记录扩展出的单词是在第几次扩展的时候得到的，key：单词，value：在广度优先搜索的第几层
steps := make(map[string]int)
steps[beginWord] = 0
// 记录了单词是从哪些单词扩展而来，key：单词，value：单词列表，这些单词可以变换到 key ，它们是一对多关系
from := make(map[string][]string)
step, found, wordLen := 1, false, len(beginWord)
queue := []string{beginWord}
for len(queue) > 0 {
size := len(queue)
for i := 0; i < size; i++ {
currWord := queue[0]
queue = queue[1:]
nextWord := currWord
// 将每一位替换成 26 个小写英文字母
for j := 0; j < wordLen; j++ {
origin := nextWord
for c := 'a'; c <= 'z'; c++ {
nextWord = nextWord[:j] + string(c) + nextWord[j+1:]
if steps[nextWord] == step {
from[nextWord] = append(from[nextWord], currWord)
}
if _, ok := data[nextWord]; !ok {
continue
}
// 如果从一个单词扩展出来的单词以前遍历过，距离一定更远，为了避免搜索到已经遍历到，且距离更远的单词，需要将它从 dict 中删除
delete(data, nextWord)
// 这一层扩展出的单词进入队列
queue = append(queue, nextWord)
// 记录 nextWord 从 currWord 而来
from[nextWord] = append(from[nextWord], currWord)
// 记录 nextWord 的 step
steps[nextWord] = step
if nextWord == endWord {
found = true
}
}
nextWord = origin
}
}
step++
if found {
break
}
}
// 第 2 步：回溯找到所有解，从 endWord 恢复到 beginWord ，所以每次尝试操作 path 列表的头部
if found {
path := []string{endWord}
res = backtrack(from, path, beginWord, endWord, res)
}
if len(res) == 0 {
return 0
}
return len(res[0])
}官方解答：
1.广度优先搜索 + 优化建图
func ladderLength(beginWord string, endWord string, wordList []string) int {
wordId := map[string]int{}
var graph [][]int
addWord := func(word string) int {
id, has := wordId[word]
if !has {
id = len(wordId)
wordId[word] = id
graph = 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.MaxInt64
dist := make([]int, len(wordId))
for i := range dist {
dist[i] = inf
}
dist[beginId] = 0
queue := []int{beginId}
for len(queue) > 0 {
v := queue[0]
queue = queue[1:]
if v == endId {
return dist[endId]/2 + 1
}
for _, w := range graph[v] {
if dist[w] == inf {
dist[w] = dist[v] + 1
queue = append(queue, w)
}
}
}
return 0
}2.双向广度优先搜索
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] = id
graph = 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.MaxInt64
distBegin := make([]int, len(wordId))
for i := range distBegin {
distBegin[i] = inf
}
distBegin[beginId] = 0
queueBegin := []int{beginId}
distEnd := make([]int, len(wordId))
for i := range distEnd {
distEnd[i] = inf
}
distEnd[endId] = 0
queueEnd := []int{endId}
for len(queueBegin) > 0 && len(queueEnd) > 0 {
q := queueBegin
queueBegin = nil
for _, 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] + 1
queueBegin = append(queueBegin, w)
}
}
}
q = queueEnd
queueEnd = nil
for _, 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] + 1
queueEnd = append(queueEnd, w)
}
}
}
}
return 0
}