> For the complete documentation index, see [llms.txt](https://shuati.gitbook.io/crack-lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://shuati.gitbook.io/crack-lintcode/linkedin/word-ladder-ii.md).

# Word Ladder II

在word Ladder 的基础上，让你输出所有的最小路径

方法：

先用bfs，建立单词之间的连接，一个是distance的map，存的是从start开始(start的distance为0),然后到词典中与他有一个字母不一样的单词，distance +1，以此类推，可以简单的理解用distance量化了 bfs 逐层遍历的层数。另一个map用来储存当前节点和他的邻居节点，邻居节点存在 map value的list里。邻居节点是所有和他只有一个字母不一样的单词，注意存的时候，按照pop出来的单词，找到所有和他只差一个单词不一样的list，把pop出来的单词分别加到这个list中的单词在map中key对应的list里。然后这个list里，把此时还不在distance 里的单词加进去，并且距离比pop出来的那个大一，因为这个单词其实就是在pop出来的单词的下一层了。

DFS：这里dfs也应用了回溯法，具体的就是，从end往前找，先把end加到path里，如果刚加到path的这个单词 等于start，那么就把path反过来，然后加到res里，再反过来（因为要回溯删掉最后一个加进去的单词，回到上层 继续遍历），如果这个单词不是start，那么就把这个单词 cur 在map中对应的list（他的邻居）取出来，并对这些邻居进行遍历，遍历时要判断他是不是在distance中存在，如果存在的话，是不是对应的距离比cur的距离小1，因为只有小1，才能保证他是在cur的上一层，这样可以去除不是最小的路径。 经过这个判断，然后对当前遍历的这个单词进行dfs递归调用。

{% embed url="<https://wdxtub.com/interview/14520607221562.html>" %}

```java
class Solution {
    public List<List<String>> findLadders(String start, String end, List<String> wordList) {
        List<List<String>> res = new ArrayList<List<String>>();
        Set<String> dict = new HashSet<>();
        
        for(String word: wordList){
            dict.add(word);
        }
        
        if(start.compareTo(end) == 0) return res;
        Set<String> visited = new HashSet<String>();
        Set<String> cur = new HashSet<String>();
        HashMap<String, ArrayList<String>> graph = new HashMap<String, ArrayList<String>>();
        graph.put(end,new ArrayList<String>());
        cur.add(start);
        boolean found = false;
        
        while (cur.isEmpty() == false && found == false) {
            Set<String> queue = new HashSet<String>();
            for(Iterator<String> it=cur.iterator();it.hasNext();) {
                visited.add(it.next());
            }
            for(Iterator<String> it=cur.iterator();it.hasNext();) {
                String str = it.next();
                char[] word = str.toCharArray();
                for (int j = 0; j < word.length; ++j) {
                    char before = word[j];
                    for (char ch = 'a'; ch <= 'z'; ++ch) {
                        if (ch == before) continue;
                        word[j] = ch;
                        String temp = new String(word);
                        if (dict.contains(temp) == false) continue;
                        if (found == true && end.compareTo(temp) != 0) continue;
                        if (end.compareTo(temp) == 0) {
                            found = true;
                            (graph.get(end)).add(str);
                            continue;
                        }
                        if (visited.contains(temp) == false) {
                            queue.add(temp);
                            if (graph.containsKey(temp) == false) {
                                ArrayList<String> l = new ArrayList<String>();
                                l.add(str);
                                graph.put(temp,l);
                            } else {
                                (graph.get(temp)).add(str);
                            }
                        }
                    }
                    word[j] = before;
                }
            }
            cur = queue;
        }
        if (found == true) {
            ArrayList<String> path = new ArrayList<String>();
            trace(res, graph, path, start, end);
        }
        return res;
        
    }
    public void trace(List<List<String>> res, 
                    HashMap<String, ArrayList<String>> graph,
                    ArrayList<String> path,
                    String start, String now) {
        path.add(now);
        if (now.compareTo(start) == 0) {
            ArrayList<String> ans = new ArrayList<String>(path);
            Collections.reverse(ans);
            res.add(ans);
            path.remove(path.size()-1);
            return;
        }
        ArrayList<String> cur = graph.get(now);
        for (int i = 0; i < cur.size(); ++i) {
            trace(res,graph,path,start,cur.get(i));
        }
        path.remove(path.size()-1);
    }
    
}
```