# Word Ladder II

> Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:
>
> 1. Only one letter can be changed at a time
> 2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

## Thoughts

参考<https://zxi.mytechroad.com/blog/searching/leetcode-126-word-ladder-ii/>

找最短距离用BFS，找具体路径用DFS。先用BFS生成地图childrens，指明从start到end每层的每个点下一步可以遍历哪些点。为了进一步刨除不能遍历的点，交替进行两头的BFS: 每次选择空间少的那个继续遍历下一层，当俩交汇时说明已经遍历到最后一层。再根据地图从start做DFS。或者用map记录节点到终点的距离，DFS时跳过不符合最短距离的点。

## Code

```
/*
 * @lc app=leetcode id=126 lang=cpp
 *
 * [126] Word Ladder II
 */
class Solution {
public:
    unordered_map<string, unordered_set<string>> bfs(unordered_set<string> &words, const string start, const string end) {
        unordered_set<string> q1({start});
        unordered_set<string> q2({end});
        unordered_map<string, unordered_set<string>> childrens;
        bool found = false, backward = false;
        while (!q1.empty() && !q2.empty() && !found) {
            for (const auto &w : q1) words.erase(w);
            for (const auto &w : q2) words.erase(w);
            unordered_set<string> nq;
            if (q1.size() > q2.size()) {
                swap(q1, q2);
                backward = !backward;
            }
            for (const auto &t : q1) {
                auto w = t;
                for (int i = 0; i < t.size(); ++i) {
                    const char ch = w[i];
                    for (char c = 'a'; c <= 'z'; ++c) {
                        w[i] = c;
                        const auto *parent = &t;
                        const auto *child = &w;
                        if (backward) swap(parent, child); 
                        if (q2.count(w)) {
                            found = true;
                            childrens[*parent].insert(*child); 
                        } else if (words.count(w)) {
                            childrens[*parent].insert(*child);
                            nq.insert(w);
                        }
                    }
                    w[i] = ch;
                }
            }
            swap(q1, nq);
        }
        return childrens;
    }

    void dfs(unordered_map<string, unordered_set<string>> &childrens, const string end, const string cur, vector<string> &path, vector<vector<string>> &res) {
        if (cur == end) {
            res.push_back(path);
            return;
        }
        for (const auto &c : childrens[cur]) {
            path.push_back(c);
            dfs(childrens, end, c, path, res);
            path.pop_back();
        }
    }

    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> words(wordList.begin(), wordList.end());
        if (!words.count(endWord)) return {};
        auto childrens = bfs(words, beginWord, endWord);
        vector<string> path({beginWord});
        vector<vector<string>> res;
        dfs(childrens, endWord, beginWord, path, res);
        return res;
    }
};


```

## Analysis

Errors:\
1\. 每次动态计算neighbors很花时间, TLE\
时间复杂度O(N), N为dict长度. 因为所生成的递归树每个节点是一个word, 最多有O(N)个节点.

## Ver.2

还可以只用BFS. 这时 **BFS存的就不再是单个的node, 而是一条path.** \
注意题意要求返回最短的路径, 也就是说所有在当前层和之前层出现过的节点都无需在未来层出现, 否则相当于在访问过某点后又重新引入该点(无论是否在同一条path), 无谓的增加了长度. 比如当前访问了 \[a, c] a的下一个点是c, 那\[a, c]和c之后将访问一样的点, 只是前者无意义的引入了a.

```
class Solution {
    // Find all next level nodes.    
    private ArrayList<String> getNeighbors(String node, Set<String> dict) {
        ArrayList<String> res = new ArrayList<String>();
        char chs[] = node.toCharArray();

        for (char ch ='a'; ch <= 'z'; ch++) {
            for (int i = 0; i < chs.length; i++) {
                if (chs[i] == ch) continue;
                    char old_ch = chs[i];
                    chs[i] = ch;
                if (dict.contains(String.valueOf(chs))) {
                    res.add(String.valueOf(chs));
                }
                chs[i] = old_ch;
            }
        }
        return res;
    }

    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> res = new ArrayList<>();
        Set<String> dict = new HashSet<String>(wordList);
        if (!dict.contains(endWord)) {
            return res;
        }
        dict.add(beginWord);
        Queue<List<String>> queue = new LinkedList<>();
        Map<String, List<String>> nodeNeighbors = new HashMap<>();

        List<String> spath = new ArrayList<>();
        spath.add(beginWord);
        queue.add(spath);
        boolean found = false;
        Set<String> wordsPerLevel = new HashSet<String>();
        while (!queue.isEmpty()) {
            if (found) {
                break;
            }
            int size = queue.size();
            wordsPerLevel.clear();
            List<List<String>> list = (List)queue;
            for (int i = 0; i < size; i++) {
                List<String> path = list.get(i);
                wordsPerLevel.add(path.get(path.size() - 1));
            }
            dict.removeAll(wordsPerLevel);

            for (int i = 0; i < size; i++) {
                List<String> path = queue.poll();
                String str = path.get(path.size() - 1);
                if (str.equals(endWord)) {
                    res.add(path);
                    found = true;
                    continue;
                }
                for (String neighbor : getNeighbors(str, dict)) {
                    List<String> newPath = new ArrayList<>(path);
                    newPath.add(neighbor);
                    queue.add(newPath);
                }
            }
        }

        return res;
    }
}
```

## Analysis

时间复杂度O(N), 最差N个word每个都访问遍


---

# 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://hao-fu-1.gitbook.io/oj/search/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.