广度优先搜索算法编程题代表——单词接龙

广度优先搜索算法编程题代表——单词接龙"/>

广度优先搜索算法编程题代表——单词接龙

广度优先搜索算法编程题代表——单词接龙

题目描述：
字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：
序列中第一个单词是 beginWord 。
序列中最后一个单词是 endWord 。
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典 wordList 中的单词。
给你两个单词 beginWord 和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。
例如：
输入：beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
输出：5
解释：一个最短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”, 返回它的长度 5。
二话不说，先看题，在题中我们不难发现这种字眼——”最短“，我们知道作为广度优先搜索算法，其最大的功能就是找最短路径，为什么？因为它是优先走离它最近的，一但满足条件，立刻停止搜索，这也就是为什么广度优先搜索为什么适合找最短路径问题了。
首先，由于一次只能变一个字母，并且转换过程中的中间单词必须是字典 wordList 中的单词，所以每次变一个字母都要和字典中的单词进行比对，这样导致了大量反复的比较，这样时间复杂度就成为了：
O(N*单词长度)
由于测试用例可能数据量相当庞大，所以极有可能超时，此时先上一个没有优化的代码：

class Solution {public int ladderLength(String beginWord, String endWord, List<String> wordList) {Queue<String>queue=new LinkedList<>();HashSet<String>set=new HashSet<>();//防止重复遍历一个单词boolean flag=false;for(String x:wordList){if(x.equals(endWord)){//有结果单词flag=true;}int count=0;for(int i=0;i<beginWord.length();++i){if(beginWord.charAt(i)!=x.charAt(i))