1392 - 单词接龙

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

  • 每一对相邻的单词只差一个字母。

  • 对于 1 <= i <= k 时,每个 si 都在 wordList 中。注意, beginWord不需要在 wordList 中。

  • sk == endWord

给你两个单词 beginWordendWord 和一个字典 wordList ,返回 beginWordendWord最短转换序列 中的 单词数目 。如果不存在这样的转换序列,返回 0

输入

第一行为2个单词,分别为beginWord和endWord

第二行为整数n,表示wordList的长度

第三行为n个单词,表示wordList的元素

输出

beginWordendWord最短转换序列 中的 单词数目

样例

输入

hit cog
6
hot dot dog lot log cog

输出

5

输入

hit cog
5
hot dot dog lot log

输出

0

提示

  • 1 <= beginWord.length <= 10

  • endWord.length == beginWord.length

  • 1 <= wordList.length <= 5000

  • wordList[i].length == beginWord.length

  • beginWordendWordwordList[i] 由小写英文字母组成

  • beginWord != endWord

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

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题