LeetCode-126：Word Ladder II

不念不忘少年蓝@ 2022-05-15 06:56 178阅读 0赞

# 题目 #

![70][]

*  题目读起来也挺简单，有一点不太清楚，就是这个字典里不包含start，但是要包含end，其实start也不所谓吧，就是end一定要有，没有就不能完成要求

# 思路 #

## 1、自己的思路 ##

*  构造图：拿每个word和别的word比较，是不是只差一个字母，是的话邻接表里添加此单词（节点）
 *  按照无向图最短路径算法求就行，Dijkstra可以
 *  最后放弃了，觉得第一步时间复杂度太高

## 2、参考实现思路 ##

*  因为用到图，所以需要很多表、容器，先介绍一下

// 记录从start到节点的距离或者花费或者说长度
    HashMap<String, Integer> costs = new HashMap<>();
    // 真正的图，记录每个点的邻接点
    HashMap<String, ArrayList<String>> graph = new HashMap<>();
    // 广度遍历的辅助队列
    ArrayDeque<String> deque = new ArrayDeque<>();
    // 需要返回的列表
    ArrayList<List<String>> ret = new ArrayList<>();
    // 记录最小花费
    int minCost = Integer.MAX_VALUE;
    // 每走一步的当前花费
    int cost = 0;

*  这里的核心是图的构造，因为直接再构造图的时候，把不符合条件的路径删去，或者说没有添加到图里边，所里这里逻辑较为复杂
 *  做一些预备工作，将字典中所有的点都添加到costs中，初始值为int能表示的最大值，让start的花费为0，在deque中添加第一个几点start
 *  首先明白deque队列的作用，如果碰到符合条件的点，就添加到队尾；逻辑主体处于一个while中，循环的条件是队不为空，while第一步就是从队头出队获得word，开始处理出队的这个节点word。
 *  接下来取得当前点的花费cost，那么他的下一个点的花费将是cost+1。
 *  然后匹配所有符合条件的邻接点，匹配的方法是遍历word的每一个位，然后将每个位从a-z变化，形成当前要处理的节点newWord，进行匹配。能否成为邻接点有诸多条件限制。第一，最基本的就是newWord在字典中存在，第二，newWord节点的花费（默认是int表示的最大的值）要比预期（cost+1）的大，这种情况其实就是在循环中，如果去匹配上一节点，那么上一节点的花费肯定是比当前预期的要小，不需要处理上一节点，第三，如果newWord的花费比预期花费要小，那就再deque中加入这个节点，等待处理，同时更新此节点的花费为cost+1，第四，如果newWord的花费和预期相同，那么说明这两个点其实处于同一水平，也就是说已经处理过，或者说是另一条路径，不需要重复处理。此处后边两种情况算是匹配成功，可以加入到图中。
 *  上边进行了匹配和更新cost，接下来将newWord添加到图（graph）中，在graph中找到newWord，在其list中添加word，这个list的含义就是可以到达newWord的上一节点。
 *  循环最后有一个小技巧，如果是最后一个点了，就记录下当前花费为最小花费minCost，配合前边的一条判断，如果当前预期花费大于minCost，那就停止循环。这样做有如下意图，如果预期花费和minCost相等，那就是另一条到达end的路径，需要处理，如果大于minCost，说明处理层次已经超过了end，不需要再往后遍历了，至于小于的情况，貌似是不会发生，其实就是这样。
 *  最后一步就是用DFS遍历一遍graph，找到所有的路径，添加到结果集ret中就可以了，这个DFS也是很简单，没什么业务逻辑，是从后往前遍历，因此用到了一个队列，每次是从左边入队，这样的效果就是形成的list从0-n节点的顺序是从start到end，处理完的节点也是从左边出队。
 *  这样就处理完了，最关键的地方还是构造图，不去处理无用的点是重点，什么样的点不需要去处理要好好理解。

# 时间复杂度 #

*  如果单词的长度是L，那么while循环的时间复杂度是O(L)，DFS的时间复杂度是(n+e)。

# 代码 #

public static List<List<String>> findLadders(String start, String end, HashSet<String> dict) {
        HashMap<String, Integer> costs = new HashMap<>();
        HashMap<String, ArrayList<String>> graph = new HashMap<>();
        ArrayDeque<String> deque = new ArrayDeque<>();
        ArrayList<List<String>> ret = new ArrayList<>();
        int minCost = Integer.MAX_VALUE;
        int cost = 0;
        
        if(dict == null || dict.size() == 0)
            return ret;
    
        for (String s : dict)
            costs.put(s, Integer.MAX_VALUE);
        costs.put(start, 0);
    
        deque.add(start);
        while (!deque.isEmpty()) {
            String word = deque.poll();
            cost = costs.get(word) + 1;
            for (int i = 0; i < word.length(); i++) {
                if (cost > minCost)
                    break;
    
                StringBuilder wordBuild = new StringBuilder(word);
                for (char c = 'a'; c <= 'z'; c++) {
                    wordBuild.setCharAt(i, c);
                    String newWord = wordBuild.toString();
                    if (!costs.containsKey(newWord))
                        continue;
                    if (cost > costs.get(newWord))
                        continue;
                    if (cost < costs.get(newWord)) {
                        deque.add(newWord);
                        costs.put(newWord, cost);
                    }
    
                    if (!graph.containsKey(newWord))
                        graph.put(newWord, new ArrayList<>());
                    graph.get(newWord).add(word);
    
                    if (end.equals(newWord)) {
                        minCost = cost;
                    }
                }
            }
        }
        
        DFS(start, end, new LinkedList<>(), graph, ret);
    
        return ret;
    }
    
    public static void DFS(String start, String word, LinkedList<String> list, HashMap<String, ArrayList<String>> graph,
            ArrayList<List<String>> ret) {
        list.offerFirst(word);
        if (start.equals(word))
            ret.add(new ArrayList<>(list));
        if (graph.containsKey(word))
            for(String s : graph.get(word))
                DFS(start, s, list, graph, ret);
        
        list.pollFirst();
    }

[70]: /images/20220515/eb882e43b1104470b93b7346c6ce75b2.png