#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 中的所有字符串 互不相同