📑 题目：127. 单词接龙

🚀 本题 LeetCode 传送门

题目大意

给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：

1. 每次转换只能改变一个字母。
2. 转换过程中的中间单词必须是字典中的单词。

说明:

• 如果不存在这样的转换序列，返回 0。
• 所有单词具有相同的长度。
• 所有单词只由小写字母组成。
• 字典中不存在重复的单词。
• 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

解题思路

• 这一题要求输出从 beginWord 变换到 endWord 最短变换次数。可以用 BFS，从 beginWord 开始变换，把该单词的每个字母都用 'a'~'z' 变换一次，生成的数组到 wordList 中查找，这里用 Map 来记录查找。找得到就入队列，找不到就输出 0 。入队以后按照 BFS 的算法依次遍历完，当所有单词都 len(queue)<=0 出队以后，整个程序结束。

• 这一题题目中虽然说了要求找到一条最短的路径，但是实际上最短的路径的寻找方法已经告诉你了：

  1. 每次只变换一个字母
  2. 每次变换都必须在 wordList 中
     所以不需要单独考虑何种方式是最短的。

代码

package leetcode
func ladderLength(beginWord string, endWord string, wordList []string) int {
 wordMap, que, depth := getWordMap(wordList, beginWord), []string{beginWord}, 0
 for len(que) > 0 {
  depth++
  qlen := len(que)
  for i := 0; i < qlen; i++ {
   word := que[0]
   que = que[1:]
   candidates := getCandidates(word)
   for _, candidate := range candidates {
    if _, ok := wordMap[candidate]; ok {
     if candidate == endWord {
      return depth + 1
     }
     delete(wordMap, candidate)
     que = append(que, candidate)
    }
   }
  }
 }
 return 0
}
func getWordMap(wordList []string, beginWord string) map[string]int {
 wordMap := make(map[string]int)
 for i, word := range wordList {
  if _, ok := wordMap[word]; !ok {
   if word != beginWord {
    wordMap[word] = i
   }
  }
 }
 return wordMap
}
func getCandidates(word string) []string {
 var res []string
 for i := 0; i < 26; i++ {
  for j := 0; j < len(word); j++ {
   if word[j] != byte(int('a')+i) {
    res = append(res, word[:j]+string(int('a')+i)+word[j+1:])
   }
  }
 }
 return res
}