LC127-单词接龙

难度困难687

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：

• 序列中第一个单词是 beginWord 。
• 序列中最后一个单词是 endWord 。
• 每次转换只能改变一个字母。
• 转换过程中的中间单词必须是字典 wordList 中的单词。

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

一句话题解
无向图中两个顶点之间的最短路径的长度，可以通过广度优先遍历得到；
为什么 BFS 得到的路径最短？可以把起点和终点所在的路径拉直来看，两点之间线段最短；
已知目标顶点的情况下，可以分别从起点和目标顶点（终点）执行广度优先遍历，直到遍历的部分有交集，这是双向广度优先遍历的思想。

详细视频解说请看

• 第一步:先将wordList梵高哈希表中,以便于判断某个单词是否在wordList
• 第二 图的遍历 广度优先遍历,必须使用队列和是否表示访问过的visited 哈希吧里
• 第三 开启广度优先遍历,包含起点,因此初始化的时候步数为1
  依次遍历当前队列中的单词
  如果currentWord 能够修改1 哥字符与endword相同,则返回step+1,程序运行结束;

package com.nie.OneJanLC;
/***@auth  wenzhao*@date 2021/1/30  10:10*/import java.util.*;public class LEE127 {public int ladderLength(String beginWord, String endWord, List<String> wordList) {//第一步:先将wordList梵高哈希表中,以便于判断某个单词是否在wordList里Set<String> wordSet = new HashSet<>(wordList);if (wordSet.size() == 0 || !wordSet.contains(endWord)) {return 0;}wordSet.remove(beginWord);//第二  图的遍历 广度优先遍历,,,必须使用队列和是否表示访问过的visited 哈希吧Queue<String> queue = new LinkedList<>();queue.offer(beginWord);Set<String> visited = new HashSet<>();visited.add(beginWord);//第三 开启广度优先遍历,包含起点,,因此初始化的时候步数为1int step = 1;while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {//依次遍历当前队列中的单词String currentWord = queue.poll();//如果currentWord 能够修改1 哥字符与endword相同,则返回step+1,程序运行结束;if (changeWordOneLetter(currentWord, queue, endWord, visited, wordSet)) {return step + 1;}}step++;}return 0;}/*** 尝试对 currentWord 修改每一个字符，看看是不是能与 endWord 匹配** @param currentWord* @param queue* @param endWord* @param visited* @param wordSet* @return*/private boolean changeWordOneLetter(String currentWord, Queue<String> queue, String endWord, Set<String> visited, Set<String> wordSet) {当前队列中的单词 转成数组char[] charArray = currentWord.toCharArray();for (int i = 0; i < endWord.length(); i++) {//先保存,在恢复char originChar = charArray[i];for (char j = 'a'; j <= 'z'; j++) {if (j == originChar) {continue;}charArray[i] = j;String nextWord = String.valueOf(charArray);if (wordSet.contains(nextWord)) {if (nextWord.equals(endWord)) {return true;}if (!visited.contains(nextWord)) {queue.add(nextWord);// 注意：添加到队列以后，必须马上标记为已经访问visited.add(nextWord);}}}charArray[i] = originChar;}return false;}
}