# 0126. Word Ladder II

<https://leetcode.com/problems/word-ladder-ii>

## Description

A **transformation sequence** from word `beginWord` to word `endWord` using a dictionary `wordList` is a sequence of words `beginWord -> s1 -> s2 -> ... -> sk` such that:

* Every adjacent pair of words differs by a single letter.
* Every `si` for `1 <= i <= k` is in `wordList`. Note that `beginWord` does not need to be in `wordList`.
* `sk == endWord`

Given two words, `beginWord` and `endWord`, and a dictionary `wordList`, return *all the **shortest transformation sequences** from* `beginWord` *to* `endWord`*, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words* `[beginWord, s1, s2, ..., sk]`.

**Example 1:**

```
**Input:** beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
**Output:** [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
**Explanation:** There are 2 shortest transformation sequences:
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"
```

**Example 2:**

```
**Input:** beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
**Output:** []
**Explanation:** The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.
```

**Constraints:**

* `1 <= beginWord.length <= 5`
* `endWord.length == beginWord.length`
* `1 <= wordList.length <= 1000`
* `wordList[i].length == beginWord.length`
* `beginWord`, `endWord`, and `wordList[i]` consist of lowercase English letters.
* `beginWord != endWord`
* All the words in `wordList` are **unique**.

## ac

```java
class Solution {
    // BFS build a directed Graph, better start from endWord, use map to circumvent loop
    // DFS find paths
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> res = new ArrayList<List<String>>(); // return result
        // build the graph
        Map<String, List<String>> graph = new HashMap<String, List<String>>(); // the graph
        Map<String, Integer> visitedMap = new HashMap<String, Integer>(); // put visited node and it's layer
        Set<String> wordSet = new HashSet<String>(wordList); // check whether dict contains word
        if (!wordSet.contains(endWord)) return res;
        wordSet.add(beginWord);

        //BFS
        Queue<String> q = new LinkedList<String>();
        q.offer(endWord);
        int layer = 0;
        int shortest = Integer.MAX_VALUE; // stop BFS
        while (!q.isEmpty()) {
            layer++;
            if (layer >= shortest) break; // shortest find, stop BFS
            int len = q.size();
            // layer by layer
            for (int i = 0; i < len; i++) {
                String start = q.poll();
                char[] chars = start.toCharArray();
                for (int k = 0; k < start.length(); k++) {
                    // construct new word
                    char old = chars[k];
                    for (char c = 'a'; c <= 'z'; c++) {
                        chars[k] = c;
                        String next = String.valueOf(chars);
                        // check new word in dict
                        if (wordSet.contains(next)) {
                            if (next == beginWord) shortest = layer + 1;
                            if (!visitedMap.containsKey(next)) {
                                // add to graph
                                List<String> tmpList = new ArrayList<String>();
                                tmpList.add(start);
                                graph.put(next, tmpList);
                                visitedMap.put(next, layer+1);
                                // add to queue for next
                                q.offer(next);
                            } else {
                                if (visitedMap.get(next) < layer + 1) {
                                    continue; // loop, give up this word 
                                } else {
                                    graph.get(next).add(start); // add to graph
                                }
                            }
                        }
                    }
                    chars[k] = old;
                }
            }
        }

        List<String> tmpRes = new ArrayList<String>(); // tmp res note for DFS
        if (!graph.containsKey(beginWord)) return res; // beginWord not even in the graph, return
        dfs(graph, beginWord, endWord, tmpRes, res);
        return res;
    }

    private void dfs(Map<String, List<String>> graph, String beginWord, String endWord, List<String> tmpRes, List<List<String>> res) {
        tmpRes.add(beginWord);
        if (beginWord.equals(endWord)) {
            res.add(new ArrayList<String>(tmpRes));
            tmpRes.remove(beginWord);
            return;
        }
        for (String s : graph.get(beginWord)) {
            // tmpRes.add(s);
            dfs(graph, s, endWord, tmpRes, res);
            // tmpRes.remove(s);
        }
        tmpRes.remove(beginWord);
    }
}
```

```java
class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> res = new ArrayList<List<String>>();
        Set<String> wordSet = new HashSet<String>(wordList);
        // edge case
        if (!wordSet.contains(endWord)) return res;
        wordSet.add(beginWord);
        wordSet.remove(endWord);  // reverse

        Map<String, List<String>> map = new HashMap<>();  // directed graph
        Map<String, Integer> visited = new HashMap<>();
        Queue<String> q = new LinkedList<>();  // BFS
        q.offer(endWord);
        int layer = 0;
        boolean findShortest = false;
        while (!q.isEmpty() && !findShortest) {
            layer++;
            int len = q.size();
            for (int i = 0; i < len; i++) {
                String h = q.poll();
                char[] chars = h.toCharArray();
                for (int j = 0; j < chars.length; j++) {
                    char old = chars[j];
                    for (char newChar = 'a'; newChar <= 'z'; newChar++) {
                        chars[j] = newChar;
                        String newWord = String.valueOf(chars);

                        if (wordSet.contains(newWord)) {
                            if (newWord.equals(beginWord)) findShortest = true;

                            if (!visited.containsKey(newWord)) {
                                map.put(newWord, new ArrayList<String>());
                                map.get(newWord).add(h);
                                q.offer(newWord);
                                visited.put(newWord, layer + 1);
                            } else {
                                if (visited.get(newWord) < layer + 1) continue;  // visited in last layer, don't go back
                                map.get(newWord).add(h);
                            }
                        }

                    }
                    chars[j] = old;
                }
            }
        }

        // build Path
        if (!map.containsKey(beginWord)) return res;
        List<String> note = new ArrayList<String>();
        note.add(beginWord);
        dfs(map, beginWord, note, res);

        return res;
    }
    private void dfs(Map<String, List<String>> map, String beginWord, List<String> note, List<List<String>> res) {
        if (!map.containsKey(beginWord)) {  // meet the end
            res.add(new ArrayList<String>(note));
            return;
        }

        for (String s : map.get(beginWord)) {
            note.add(s);
            dfs(map, s, note, res);
            note.remove(note.size() - 1);
        }
    }
}

/*
build graph backwards
dfs get result

*/
```


---

# 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://jaywin.gitbook.io/leetcode/solutions/0126-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.