按字典 wordList 完成从单词 beginWord 到单词 endWord 转化，一个表示此过程的 转换序列 是形式上像 beginWord -> s1 -> s2 -> … -> sk 这样的单词序列，并满足：
每对相邻的单词之间仅有单个字母不同。
转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词。注意，beginWord 不必是字典 wordList 中的单词。
sk == endWord
给你两个单词 beginWord 和 endWord ，以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列 ，如果不存在这样的转换序列，返回一个空列表。每个序列都应该以单词列表 [beginWord, s1, s2, …, sk] 的形式返回。
示例 1：
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
解释：存在 2 种最短的转换序列：
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"示例 2：
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：[]
解释：endWord "cog" 不在字典 wordList 中，所以不存在符合要求的转换序列。提示：
- 1 <= beginWord.length <= 5
- endWord.length == beginWord.length
- 1 <= wordList.length <= 500
- wordList[i].length == beginWord.length
- beginWord、endWord 和 wordList[i] 由小写英文字母组成
- beginWord != endWord
- wordList 中的所有单词 互不相同
解题：
// 不会啊。。。官方解答：
1.广度优先搜索 + 回溯
// 官方没有go代码，根据Java写的
func findLadders(beginWord string, endWord string, wordList []string) [][]string {
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 res
}
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)
}
return res
}
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
}