#GT009. 单词接龙

单词接龙

说明

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk

  • 每一对相邻的单词只差一个字母。
  •  对于 1 <= i <= k 时,每个 si 都在 wordList 中。注意, beginWord 不需要在 wordList 中。
  • sk == endWord

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

输入格式

第一行一个整数 n,即 wordList 的长度

第二行两个单词 beginWord 和 endWord

第三行 n 个单词 s1

输出格式

一个整数,即从 beginWord 到 endWord 的最短转换长度

样例

6
hit cog
hot dot dog lot log cog
5

提示

数据范围
  • 1 <= beginWord.length <= 10
  • endWord.length == beginWord.length
  • wordList[i].length == beginWord.length
  • 1 <= n<= 5000
  • beginWord、endWord 和 wordList[i] 由小写英文字母组成
  • beginWord != endWord
  • wordList 中的所有字符串 互不相同