# Word Ladder II

Given two words (beginWordandendWord), and a dictionary's word list, find all shortest transformation sequence(s) frombeginWordtoendWord, such that:

1. Only one letter can be changed at a time
2. Each transformed word must exist in the word list. Note tha beginWord is not a transformed word.

For example,

Given:\
beginWord=`"hit"`\
endWord=`"cog"`\
wordList=`["hot","dot","dog","lot","log","cog"]`

Return

```
  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]
```

分析

* BFS得到所有最短路径， DFS遍历输出
* BFS 其中用map father保存路径，用字典里所有words做key，然后存储所有可到word的father点，father放在list里。
* Distance用法妙极，在BFS里可以判重，在DFS里判断最短路径。
* BFS里第一次遇到的word直接存入distance里，因为将来再遇到只会路径只会更长。同时也用来判重，再者distance不像father里所有字典里的word都在father的keyset里。distance里不一定包含字典里所有words，因为word不一定可达。
* DFS里Collections.reverse(List l)

```
class Solution {
    Map<String,List<String>> father = new HashMap<String,List<String>>();
    Map<String, Integer> distance = new HashMap<String, Integer>();

    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> ret = new ArrayList<>();
        if(!wordList.contains(endWord))
            return ret;

        List<String> path = new ArrayList<String>();
        wordList.add(beginWord);
        // wordList.add(endWord);
        bfs(beginWord, endWord, wordList);
        dfs(ret, path, endWord, beginWord);
        return ret;
    }
    void dfs(List<List<String>> ret, List<String> path, String s, String e){
        path.add(s);
        if(s.equals(e)){
            List<String> nl = new ArrayList<String>(path);
            Collections.reverse(nl);
            ret.add(nl);
        }else{
            for(String f : father.get(s)){
                //distance来找到合适的father。
                if(distance.containsKey(f) && distance.get(s) == distance.get(f) + 1){
                    dfs(ret, path, f, e);
                }
            }

        }
        path.remove(path.size() - 1);
    }

    List<String> getNextWord(String cur, Set
                             <String> wordList){
        List<String> ret = new ArrayList<String>();
        char[] cs = cur.toCharArray();
        for(int i = 0; i < cur.length(); i ++){                   
            for(char c = 'a' ; c <= 'z'; c ++){
                if(cs[i] == c){
                    continue;
                }                    
                char temp = cs[i];
                cs[i] = c;
                String nw = new String(cs);                
                if(wordList.contains(nw)){
                    ret.add(nw);
                }
                cs[i] = temp;
            }                
        } 
        return ret;
    }

    void bfs(String beginWord, String endWord, List<String> wordList){
        Queue<String> q = new LinkedList<String>();
        //用set存字典，为了让查contains更快
        Set<String> dict = new HashSet<>();        
        for (String word : wordList) {
            father.put(word, new ArrayList<String>());
            dict.add(word);
        }
        q.add(beginWord);
        distance.put(beginWord, 0);

        while(!q.isEmpty()){          
            String cur = q.poll();
            List<String> nextWords = getNextWord(cur, dict);
            for(String s : nextWords){
                father.get(s).add(cur);//新的word都是在字典里的，所以father不必判断，可以得到所有情况
                if(!distance.containsKey(s)){//字典里并非所有字母都可达，所以需要判断，这里也是为了去重。
                   distance.put(s, distance.get(cur) + 1);//第一个到的就是最短的，后来的不要再加了，会越来越大的。
                    q.offer(s); 
                }

            }
        }

    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nataliekung.gitbook.io/ladder_code/l9tu-he-sou-suo/word-ladder-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.