LeetCode 126 单词接龙 II

按字典 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
}