127. 单词接龙

[yankewei]

给定两个单词（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" 不在字典中，所以无法进行转换。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-ladder

解答

package main

import "fmt"

type queueItem struct {
	Item  string
	Level int
}

func main() {
	beginWord, endWord := "hit", "dog"
	wordList := []string{"hot", "dot", "dog", "lot", "log", "cog"}
	fmt.Println(ladderLength(beginWord, endWord, wordList))
}

func ladderLength(beginWord string, endWord string, wordList []string) int {
	// 如果单词表中不包含endWord，直接返回0
	if !isItemExist(endWord, wordList) {
		return 0
	}
	length := len(endWord)
	allComboDict := make(map[string][]string, length)
	for _, v := range wordList {
		for i := 0; i < length; i++ {
			key := v[0:i] + "*" + v[i+1:]
			allComboDict[key] = append(allComboDict[key], v)
		}
	}
	wordScaned := make(map[string]bool)

	queue := []queueItem{queueItem{beginWord, 1}}
	for len(queue) != 0 {
		item := queue[0]
		word := item.Item
		queue = queue[1:]
		if _, e := wordScaned[word]; e {
			continue
		}
		for i := 0; i < length; i++ {
			key := word[0:i] + "*" + word[i+1:]
			wordScaned[word] = true
			for _, v := range allComboDict[key] {
				if endWord == v {
					return item.Level + 1
				}
				queue = append(queue, queueItem{v, item.Level + 1})
			}
		}
	}
	return 0
}

func isItemExist(s string, wordList []string) bool {
	for _, v := range wordList {
		if v == s {
			return true
		}
	}
	return false
}