参考资料：
https://leetcode-cn.com/problems/word-ladder-ii/
https://www.jianshu.com/p/2061194d355e
通过阅读题意，我们知道这个题目就是图的最短路径，只不过要记录下整个路径过程。图的最短路径有Dijkstra算法和BFS，只不过BFS在遍历的时候要注意防止重复。Dijkstra算是就是一种BFS，只不过BFS每次是遍历一层，Dijkstra算法每次是遍历最近的一个。
我们这里采用BFS更加清晰一点，这里的关键在于如何防止重复。
每个路径想要不重复走入重复，最直观的想法是给每个路径添加一个set集合，保存之前走过的路径，这样的成本太高，可能会造成超时。
这里我们可以采用Dijkstra的costs数组，这个数组保存了目前为止从起点到各个终点之间的最短路径，如果同一条路径之前到过A点，下次自然不会再进入A点，这个效果跟上面的方法是一样的。但是更妙的来了，其他路径如果到A点的路径长度大于之前路径到A点的路径长度也不会进入A，也就是只有一条路径会经过A，让这条路径经过A去探索到达终点的路径，避免了更多重复，除非有找到更近的A。还有更妙的，我们不怕到终点有冗余的路径，因为我们前面说了cost能保证到其他点的路径都是最短的，所以下面我们一个个遍历也是可以的，请看第二段代码。
这样我们的代码就跟Dijkstra算法一样了，除了Dijkstra算法每次需要找加入最短路径对应的节点，而我们因为节点之间的路径都是1，所以最短的都是排在前面的，所以不用这样的额外操作。
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
List<List<String>> results = new LinkedList<>();
LinkedList<LinkedList<String>> lastVisitedLadder = new LinkedList<>();
Set<String> wordSet = wordList.stream().collect(Collectors.toSet());
if (!wordSet.contains(endWord)) {
return results;
}
LinkedList<String> beginLadder = new LinkedList<>();
beginLadder.add(beginWord);
lastVisitedLadder.add(beginLadder);
// costs 是画龙点睛之笔，costs 是为了减少在图的遍历过程中的重复遍历，就像Dijsktra中的costs数组一样
Map<String, Integer> costs = wordList.stream().collect(Collectors.toMap(x -> x, x -> Integer.MAX_VALUE));
costs.put(beginWord, 0);
while (!lastVisitedLadder.isEmpty()) {
boolean foundEndWord = false;
int size = lastVisitedLadder.size();
for (int i = 0; i < size; i++) {
LinkedList<String> visitedLadder = lastVisitedLadder.remove();
String lastWord = visitedLadder.getLast();
for (String word : wordSet) {
int cost = costs.get(lastWord) + 1;
if (cost <= costs.get(word) && isNext(lastWord, word)) {
costs.put(word, cost);
if(word.equals(endWord)) {
foundEndWord = true;
LinkedList<String> newLadder = new LinkedList<>(visitedLadder);
newLadder.add(word);
results.add(newLadder);
}
LinkedList<String> newLadder = new LinkedList<>(visitedLadder);
newLadder.add(word);
lastVisitedLadder.add(newLadder);
}
}
}
System.out.println(lastVisitedLadder.size());
if (foundEndWord) {
break;
}
}
return results;
}
去掉BFS的每层forsize循环
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
List<List<String>> results = new LinkedList<>();
LinkedList<LinkedList<String>> lastVisitedLadder = new LinkedList<>();
Set<String> wordSet = wordList.stream().collect(Collectors.toSet());
if (!wordSet.contains(endWord)) {
return results;
}
LinkedList<String> beginLadder = new LinkedList<>();
beginLadder.add(beginWord);
lastVisitedLadder.add(beginLadder);
// costs 是画龙点睛之笔，costs 是为了减少在图的遍历过程中的重复遍历，就像Dijsktra中的costs数组一样
Map<String, Integer> costs = wordList.stream().collect(Collectors.toMap(x -> x, x -> Integer.MAX_VALUE));
costs.put(beginWord, 0);
while (!lastVisitedLadder.isEmpty()) {
boolean foundEndWord = false;
LinkedList<String> visitedLadder = lastVisitedLadder.remove();
String lastWord = visitedLadder.getLast();
for (String word : wordSet) {
int cost = costs.get(lastWord) + 1;
if (cost <= costs.get(word) && isNext(lastWord, word)) {
costs.put(word, cost);
if(word.equals(endWord)) {
foundEndWord = true;
LinkedList<String> newLadder = new LinkedList<>(visitedLadder);
newLadder.add(word);
results.add(newLadder);
}
LinkedList<String> newLadder = new LinkedList<>(visitedLadder);
newLadder.add(word);
lastVisitedLadder.add(newLadder);
}
}
}
return results;
}
网友评论