127. 单词接龙
难度: 困难
字典 wordList
中从单词 beginWord
和 endWord
的 转换序列 是一个按下述规格形成的序列:
- 序列中第一个单词是
beginWord
。 - 序列中最后一个单词是
endWord
。 - 每次转换只能改变一个字母。
- 转换过程中的中间单词必须是字典
wordList
中的单词。
给你两个单词 beginWord
和 endWord
和一个字典 wordList
,找到从 beginWord
到 endWord
的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列,返回 0。
示例 1:
1 | 输入:beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] |
示例 2:
1 | 输入:beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] |
提示:
1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord
、endWord
和wordList[i]
由小写英文字母组成beginWord != endWord
wordList
中的所有字符串 互不相同
方法一:广度优先搜索+优化建图
利用map维护一个链表,每个链表中对应当前元素的转移状态
1 | class Solution { |
方法二:双向广度优先搜索
如果使用两个同时进行的广搜可以有效地减少搜索空间。一边从 beginWord 开始,另一边从 endWord 开始。我们每次从两边各扩展一层节点,当发现某一时刻两边都访问过同一顶点时就停止搜索。这就是双向广度优先搜索,它可以可观地减少搜索空间大小,从而提高代码运行效率。
1 | class Solution { |
参考文献
作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/word-ladder/solution/dan-ci-jie-long-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。