前言
持续更新了
正文
问题来源
本问题来自leetcode上的127题。
问题描述
给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
说明:
如果不存在这样的转换序列，返回 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" 不在字典中，所以无法进行转换。
分析：
第一步：根据字符串相差为1认为可达，抽象成为邻接表表示的无向图；
第二步：根据广度搜索计算最短距离
type node struct {
word int
level int
}
func distance1(s1, s2 string) bool { // 用于判断两个字符串是否距离为1
count := 0
for i := 0; i < len(s1); i++ {
if s1[i] != s2[i] {
count++
}
}
return count == 1
}
func ladderLength(beginWord string, endWord string, wordList []string) int {
// 判断endWord是否在wordList中，并记录其位置
e := -1
for i, v := range wordList {
if v == endWord {
e = i
break
}
}
if e < 0 {
return 0
}
e++ // 为0的特别标记为beginWord
// 构建邻接表表示的无向图
m := make([][]int, len(wordList)+1)
for i := 0; i <= len(wordList); i++ {
for j := 0; j <= len(wordList); j++ {
var a, b string
if i == 0 {
a = beginWord
} else {
a = wordList[i-1]
}
if j == 0 {
b = beginWord
} else {
b = wordList[j-1]
}
if distance1(a, b) {
m[i] = append(m[i], j)
}
}
}
// 下标为0的为beginWord
queue := make([]node, 0)
queue = append(queue, node{0,1})
visited := make(map[int]bool)
visited[0] = true
for len(queue) > 0 {
n := queue[0]
queue = queue[1:]
word := n.word
level := n.level
for i := 0; i < len(m[word]); i++ {
w := m[word][i]
if w == e {
return level+1
}
if visited[w] {
continue
}
queue = append(queue, node{w, level+1})
visited[w] = true
}
}
return 0
}
总结：
勤思考。
结语
不管怎么样好好加油。
