剑指OfferII108.单词演变

题目

在字典（单词列表） wordList 中，从单词 beginWord 和 endWord 的转换序列是一个按下述规格形成的序列：

序列中第一个单词是 beginWord 。

序列中最后一个单词是 endWord 。

每次转换只能改变一个字母。

转换过程中的中间单词必须是字典 wordList 中的单词。

给定两个长度相同但内容不同的单词 beginWord 和 endWord 和一个字典 wordList ，

找到从 beginWord 到 endWord 的最短转换序列中的单词数目。如果不存在这样的转换序列，返回 0。

示例 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 <= beginWord.length <= 10

endWord.length == beginWord.length

1 <= wordList.length <= 5000

wordList[i].length == beginWord.length

beginWord、endWord 和 wordList[i] 由小写英文字母组成

beginWord != endWord

wordList 中的所有字符串互不相同

注意：本题与主站 127 题相同：

解题思路分析

1、广度优先搜索；时间复杂度O(n^2)，空间复杂度O(n^2)

func ladderLength(beginWord string, endWord string, wordList []string) int {
   m := make(map[string]int)
   for i := 0; i < len(wordList); i++ {
      m[wordList[i]] = 1
   }
   if m[endWord] == 0 {
      return 0
   }
   preMap := make(map[string][]string)
   for i := 0; i < len(wordList); i++ {
      for j := 0; j < len(wordList[i]); j++ {
         newStr := wordList[i][:j] + "*" + wordList[i][j+1:]
         if _, ok := preMap[newStr]; !ok {
            preMap[newStr] = make([]string, 0)
         }
         preMap[newStr] = append(preMap[newStr], wordList[i])
      }
   }
   visited := make(map[string]bool)
   count := 0
   queue := make([]string, 0)
   queue = append(queue, beginWord)
   for len(queue) > 0 {
      count++
      length := len(queue)
      for i := 0; i < length; i++ {
         for j := 0; j < len(beginWord); j++ {
            newStr := queue[i][:j] + "*" + queue[i][j+1:]
            for _, word := range preMap[newStr] {
               if word == endWord {
                  return count + 1
               }
               if visited[word] == false {
                  visited[word] = true
                  queue = append(queue, word)
               }
            }
         }
      }
      queue = queue[length:]
   }
   return 0
}

2、广度优先搜索；时间复杂度O(n^2)，空间复杂度O(n^2)

func ladderLength(beginWord string, endWord string, wordList []string) int {
   m := make(map[string]int)
   for i := 0; i < len(wordList); i++ {
      m[wordList[i]] = 1
   }
   if m[endWord] == 0 {
      return 0
   }
   queue := make([]string, 0)
   queue = append(queue, beginWord)
   count := 0
   for len(queue) > 0 {
      count++
      length := len(queue)
      for i := 0; i < length; i++ {
         for _, word := range wordList {
            diff := 0
            for j := 0; j < len(queue[i]); j++ {
               if queue[i][j] != word[j] {
                  diff++
               }
               if diff > 1 {
                  break
               }
            }
            if diff == 1 && m[word] != 2 {
               if word == endWord {
                  return count + 1
               }
               m[word] = 2
               queue = append(queue, word)
            }
         }
      }
      queue = queue[length:]
   }
   return 0
}