单词接龙 II——Dijkstra算法与BFS

参考资料：
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;
    }