LeetCode-126.单词接龙II(相关话题:Dijkstra算法+深度优先)
给定两个单词(beginWord 和 endWord)和一个字典 wordList,找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则:
每次转换只能改变一个字母。 转换过程中的中间单词必须是字典中的单词。 说明:
- 如果不存在这样的转换序列,返回一个空列表。
- 所有单词具有相同的长度。
- 所有单词只由小写字母组成。
- 字典中不存在重复的单词。
- 你可以假设 beginWord 和 endWord 是非空的,且二者不相同。
示例 1:
输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
输出:
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
示例 2:
输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
输出: []
解释: endWord "cog" 不在字典中,所以不存在符合要求的转换序列。
Dijkstra算法:算法运行过程中,维持一个数组(最小优先队列),数组中记录起点到每个节点的最短路径
在这道题中(相当于每条边权值均为1的有向图),用Map记录单词字典中每个单词至beginWord的最短路径(即beginWord最少需要经过多少次才能转换为字典中的每个单词)
同时,在Dijkstra算法计算最短路径的过程中,用Map> relation记录单词字典中每个单词的父节点(前一单词),处理规则如下:如上图中,由结点2更新与结点2相邻的结点(即结点3),由于1+2=3小于4(之前到结点3的最短路径),因此将relation中结点3的父节点list清空再将结点2放进去;若结点1到结点3的边的权值为3,由结点2更新结点3时,由于1+2=3,与之前到结点3的最短路径相等,因此可直接将结点1添加至relation中结点3的父节点list中(其中已经有结点2);若relation中不存在key-结点3(即结点1不与结点3直接相连),直接将结点3和包含结点2的list放入relation中
计算完单词字典中每个单词的父节点(前一单词)后,用深度优先遍历,从endWord开始倒推出最短转换路径
注意:在Dijkstra算法计算过程中,由于需要每次从未访问的结点中求出最短路径最小的结点,以更新周围直接相连的结点,需要最小优先队列来每次获取当前路径最短的结点,但这个题中,由于每条边的权值均为1,因此可按照访问到的顺序将单词放入队列中,按照访问顺序取出的单词,一定是当前未访问结点的最短路径,可提高效率。
Java代码:
class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
/**
* Dijkstra算法
* 1.用Map<String, Integer>维护每个元素到起点的长度,初始为∞
* 2.用Map<String, List<String>>维护每个节点最短路径的前一节点
*/
Queue<String> queue = new java.util.concurrent.LinkedBlockingQueue<>();
Map<String, Integer> dis = new HashMap<>();
Map<String, List<String>> relation = new HashMap<>();
dis.put(beginWord, 0);
queue.add(beginWord);
while(!queue.isEmpty()){
// 获取未访问节点中,路径最短的节点,所有边的权重为1
String str = queue.poll();
int minPath = dis.get(str);
// 更新与未访问节点中路径最短节点相邻节点的最短路径,同时记录节点的最短路径前一节点
for(String key: wordList){
// 判断两个节点是否相邻
int k = 0;
for(int i = 0; i < key.length(); i++){
if(str.charAt(i) != key.charAt(i))
k++;
if(1 < k)
break;
}
// 相邻节点,更新最短路径,同时记录节点的最短路径前一节点
if(1 == k){
if(null == relation.get(key) || null == dis.get(key) || minPath+1 < dis.get(key)){
List<String> re = new ArrayList<>();
re.add(str);
relation.put(key, re);
} else {
if(minPath+1 == dis.get(key))
relation.get(key).add(str);
}
if(!dis.containsKey(key))
queue.add(key);
dis.put(key, Math.min(minPath+1, null == dis.get(key) ? Integer.MAX_VALUE : dis.get(key)));
}
}
// 剔除已访问过节点
dis.remove(str);
wordList.remove(str);
}
List<List<String>> res = new LinkedList<>();
LinkedList<String> tmp = new LinkedList<>();
tmp.addFirst(endWord);
dfs(endWord, tmp, relation, res, beginWord);
return res;
}
private void dfs(String cur, LinkedList<String> tmp, Map<String, List<String>> relation, List<List<String>> res, String beginWord){
if(cur.equals(beginWord)){
res.add(new LinkedList<>(tmp));
return;
}
if(!relation.containsKey(cur))
return;
List<String> pre = relation.get(cur);
for(int i = 0; i < pre.size(); i++){
cur = pre.get(i);
tmp.addFirst(cur);
dfs(cur, tmp, relation, res, beginWord);
tmp.removeFirst();
}
}
}