代码随想录——单词接龙（图论）

题目

字典 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” 不在字典中，所以无法进行转换

思路

以实例一为例子，可以看出hit到cog的路线，不止一条，有三条，一条是最短的长度为5，两条长度为6

本题只需要求出最短长度就可以了，不用找出路径

本题有两个问题：

1. 图中的线是如何连在一起的
2. 起点和终点的最短路径长度

首先题目中并没有给出点与点之间的连线，而是要我们自己去连，条件是字符只能差一个，所以判断点与点之间的关系，要自己判断是不是差一个字符，如果差一个字符，那就是有连接，即如果两个单词可以只改变一个字母进行转换，那么说明他们之间有一条双向边

然后就是求起点和终点的最短路径长度，这里无向图求最短路，求最短，立即推—>广搜，广搜只要到达终点，就一定是最短的路径。因为广搜就是以起点中心向四周扩散的搜索。

另外要注意的点就是

• 本题是一个无向图，需要使用标记位，标记节点是否走过，防止死循环
• 本题给出的集合是数组型的，可以转成set结构，查找更快

java代码如下：

class Solution {
	public int  ladderLength(String beginWord ,String endWord, List<String> wordList){
		HashSet<String> wordSet = new HashSet<>(wordList);
		if(wordSet.size() == 0 || !wordSet.contains(endWord)){//endWord不在字典中，就无法进行转换
			return 0;
		}
		Queue<String> que = new LinkedList<>();//bfs 队列
		que.offer(beginWord);//起始元素入队
		Map<String,Integer> map = new HashMap<>();//记录单词对应路径长度,映射关系
		map.put(beginWord,1);//初始化
		
		while(!que.isEmpty()){
			String word = que.poll();//取出队头单词
			int path = map.get(word);//获取到该单词的路径长度
			for(int i = 0; i < word.length(); i++){//遍历单词的每个字符
				char[] chars = word.toCharArray();//将单词转换为char array，方便替换
				for(char k = 'a'; k <= 'z'; k++){//从'a' 到 'z' 遍历替换
					chars[i] = k;替换第i个字符,注意这里是每次是一个位置替换一个字符,保证有边，因为只有一次改一个字符才能算有边
					String newWord = String.valueOf(chars);//得到新的字符串
					if(newWord.equals(endWord)){//只要转成功了，就返回当前路径加一,如果没有转成功，就去判断是否转成了中间单词，即下面的if条件
						return path + 1;
					}
					if(wordSet.contains(newWord) && !map.containsKey(newWord)){如果替换后的新单词在set中(即转成了中间单词)，并且没有访问过
						map.put(newWord,path + 1);//记录这个中间单词对应的路径长度，相当于标记访问过了
						que.offer(newWord);//入队，继续下一轮判断，即对这个newWrod继续替换一个字符进行下去					
					}
				}
			}
		}
		return 0;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32