题目描述

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

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

说明:

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

示例 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" 不在字典中，所以无法进行转换。

算法

首先写一个函数diffWord(beginWord,endWord string)bool用来判断两个单词是否只差距一个字符，我们接下来需要用到这个函数

然后开始我们的算法

我们的核心思想是找出字典中每一个单词到endWord的距离，从而找出beginWord到endWord的最短距离

• 创建一个map[string]int用来保存该单词到最后一个单词的距离，如果字典中存在单词endWord，那么就将map初始化为map[endWord]=1，此时的距离dis=1，相反如果字典中不存在最后单词endWord，那么就直接返回0
• 我们将字典中所有到最后单词endWord距离为dis的单词保存在一个切片中，并且将他们从map中去除，然后判断开始单词beginWord是否和此时切片中某个单词只相差一个字符，如果只相差一个字符，那么就返回结果dis+1
• 如果切片中单词没有和beginWord只相差一个字符的单词，那么我们就继续计算map中值为0的单词。
  • 如果map中剩余的单词和切片中单词只差一个字符，那么将他在map中的值设置为dis+1
  • 如果map中没有和切片中任何单词只差一个字符，那么就返回0
  • 将dis的值加1

代码

func ladderLength(beginWord string, endWord string, wordList []string) int {
	if beginWord == endWord {
		return 1
	}
	wordMap := make(map[string]int)
	for _, word := range wordList {
		wordMap[word] = 0
	}
	if _, ok := wordMap[endWord]; ok {
		wordMap[endWord] = 1
	} else {
		// endWord不在字典中
		return 0
	}
	// 当前已经计算的初始最短距离的单词距离是1
	dis := 1
	for {
		var disWords []string
		for word, curDis := range wordMap {
			if curDis > 0 {
				delete(wordMap, word)
			}
			if curDis == dis {
				if diffWord(beginWord, word) {
					return dis + 1
				}
				disWords = append(disWords, word)
			}
		}
		// 没有在当前能够到达最后单词的序列中找到能够到达的
		// 如果当前所有单词都已经找了，那么就返回0
		// 如果链条断开，也返回0
		retFlag := true
		// 查找是否还有没有计算长度的单词
		for word := range wordMap {
			// 检查word是否和disWords中的单词只差距一个字符
			for _, subWord := range disWords {
				if diffWord(word, subWord) {
					retFlag = false
					wordMap[word] = dis + 1
				}
			}
		}
		dis++
		if retFlag {
			return 0
		}
	}
}
func diffWord(beginWord, endWord string) bool {
	res := false
	for i := 0; i < len(beginWord); i++ {
		if beginWord[i] != endWord[i] {
			if !res {
				res = !res
			} else {
				return !res
			}
		}
	}
	return res
}