# 单词接龙 II

<p>按字典 <code>wordList</code> 完成从单词 <code>beginWord</code> 到单词 <code>endWord</code> 转化，一个表示此过程的 <strong>转换序列</strong> 是形式上像 <code>beginWord -> s<sub>1</sub> -> s<sub>2</sub> -> ... -> s<sub>k</sub></code> 这样的单词序列，并满足：</p>

<div class="original__bRMd">
<div>
<ul>
	<li>每对相邻的单词之间仅有单个字母不同。</li>
	<li>转换过程中的每个单词 <code>s<sub>i</sub></code>（<code>1 <= i <= k</code>）必须是字典 <code>wordList</code> 中的单词。注意，<code>beginWord</code> 不必是字典 <code>wordList</code> 中的单词。</li>
	<li><code>s<sub>k</sub> == endWord</code></li>
</ul>

<p>给你两个单词 <code>beginWord</code> 和 <code>endWord</code> ，以及一个字典 <code>wordList</code> 。请你找出并返回所有从 <code>beginWord</code> 到 <code>endWord</code> 的 <strong>最短转换序列</strong> ，如果不存在这样的转换序列，返回一个空列表。每个序列都应该以单词列表<em> </em><code>[beginWord, s<sub>1</sub>, s<sub>2</sub>, ..., s<sub>k</sub>]</code> 的形式返回。</p>

<p> </p>

<p><strong>示例 1：</strong></p>

<pre>
<strong>输入：</strong>beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
<strong>输出：</strong>[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
<strong>解释：</strong>存在 2 种最短的转换序列：
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"
</pre>

<p><strong>示例 2：</strong></p>

<pre>
<strong>输入：</strong>beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
<strong>输出：</strong>[]
<strong>解释：</strong>endWord "cog" 不在字典 wordList 中，所以不存在符合要求的转换序列。
</pre>

<p> </p>

<p><strong>提示：</strong></p>

<ul>
	<li><code>1 <= beginWord.length <= 7</code></li>
	<li><code>endWord.length == beginWord.length</code></li>
	<li><code>1 <= wordList.length <= 5000</code></li>
	<li><code>wordList[i].length == beginWord.length</code></li>
	<li><code>beginWord</code>、<code>endWord</code> 和 <code>wordList[i]</code> 由小写英文字母组成</li>
	<li><code>beginWord != endWord</code></li>
	<li><code>wordList</code> 中的所有单词 <strong>互不相同</strong></li>
</ul>
</div>
</div>

<p>以下错误的选项是？</p>

## aop
### before
```cpp
#include <bits/stdc++.h>
using namespace std;
```
### after
```cpp
int main()
{
    Solution sol;
    vector<vector<string>> res;
    string beginWord = "hit", endWord = "cog";
    vector<string> wordList = {"hot", "dot", "dog", "lot", "log", "cog"};
    res = sol.findLadders(beginWord, endWord, wordList);
    for (auto i : res)
    {
        for (auto j : i)
            cout << j << " ";
        cout << endl;
    }
    return 0;
}
```

## 答案
```cpp
class Solution
{
public:
    unordered_map<string, vector<string>> tree;
    vector<vector<string>> ans;

    void dfs(vector<string> &cur, string curWord, string endWord)
    {
        if (curWord == endWord)
        {
            ans.push_back(cur);
            return;
        }
        for (string s : tree[curWord])
        {
            cur.push_back(s);
            dfs(cur, s, endWord);
            cur.pop_back();
        }
    }

    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string> &wordList)
    {
        if (wordList.size() == 0 || find(wordList.begin(), wordList.end(), endWord) == wordList.end())
            return {};
        unordered_set<string> bfsFromBegin{beginWord};
        unordered_set<string> bfsFromEnd{endWord};
        unordered_set<string> dirc(wordList.begin(), wordList.end());
        bool findFlag = false, reverseFlag = false;
        while (!bfsFromBegin.empty())
        {
            unordered_set<string> next;
            for (string s : bfsFromBegin)
                dirc.erase(s);
            for (string s1 : bfsFromBegin)
            {
                for (int i = 0; i < s1.size(); ++i)
                {
                    string s2 = s1;
                    for (char c = 'a'; c <= 'z'; ++c)
                    {
                        s2[i] = c;
                        if (dirc.count(s2) == 0)
                            continue;
                        next.insert(s2);
                    }
                    reverseFlag ? tree[s2].push_back(s1) : tree[s1].push_back(s2);
                }
            }
            bfsFromBegin = next;
            if (bfsFromBegin.size() > bfsFromEnd.size())
            {
                reverseFlag = !reverseFlag;
                swap(bfsFromBegin, bfsFromEnd);
            }
            if (findFlag)
                break;
        }
        vector<string> cur = {beginWord};
        dfs(cur, beginWord, endWord);
        return ans;
    }
};
```
## 选项

### A
```cpp
class Solution
{
public:
    bool differ_one(string &s, string &t)
    {
        int n = 0;
        for (int i = 0; i < s.size(); ++i)
            if ((n += s[i] != t[i]) > 1)
                return false;
        return n == 1;
    }
    vector<vector<int>> fa;
    vector<string> tmp;
    vector<vector<string>> ans;
    void dfs(int index, vector<string> &wordList)
    {
        if (fa[index].empty())
        {
            reverse(tmp.begin(), tmp.end());
            ans.push_back(tmp);
            reverse(tmp.begin(), tmp.end());
        }
        for (auto &x : fa[index])
        {
            tmp.push_back(wordList[x]);
            dfs(x, wordList);
            tmp.pop_back();
        }
    }
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string> &wordList)
    {

        int b = -1, e = -1, x;
        for (int i = 0; i < wordList.size(); ++i)
        {
            if (wordList[i] == beginWord)
                b = i;
            if (wordList[i] == endWord)
                e = i;
        }
        if (e == -1)
            return ans;
        if (b == -1)
            wordList.push_back(beginWord), b = wordList.size() - 1;
        queue<int> que;
        fa.assign(wordList.size(), vector<int>());
        vector<int> index(wordList.size(), 0);
        que.push(b), index[b] = 1;
        while (!que.empty())
        {
            x = que.front(), que.pop();
            if (index[e] && index[x] >= index[e])
                break;
            for (int i = 0; i < wordList.size(); ++i)
                if ((index[i] == 0 || index[x] + 1 == index[i]) && differ_one(wordList[x], wordList[i]))
                    if (index[i] == 0)
                        index[i] = index[x] + 1, que.push(i), fa[i].push_back(x);
                    else
                        fa[i].push_back(x);
        }
        if (index[e] == 0)
            return ans;
        tmp.push_back(endWord);
        dfs(e, wordList);
        tmp.pop_back();
        return ans;
    }
};
```

### B
```cpp
class Solution
{
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string> &wordList)
    {
        unordered_set<string> list(wordList.begin(), wordList.end());
        if (!list.count(endWord))
            return {};

        unordered_map<string, unordered_set<string>> trace;

        unordered_set<string> p;
        unordered_set<string> q{beginWord};

        while (q.size() && !trace.count(endWord))
        {

            for (auto w : q)
            {
                list.erase(w);
            }
            p.clear();

            for (auto str : q)
            {
                for (int i = 0; i < str.size(); ++i)
                {
                    string tmp = str;
                    for (char c = 'a'; c <= 'z'; ++c)
                    {
                        tmp[i] = c;

                        if (list.find(tmp) == list.end())
                            continue;

                        trace[tmp].insert(str);

                        p.insert(tmp);
                    }
                }
            }

            q = p;
        }

        if (!trace.size())
            return {};
        vector<vector<string>> res;

        dfs(res, {}, trace, endWord);
        return res;
    }

    void dfs(vector<vector<string>> &res, vector<string> path, unordered_map<string, unordered_set<string>> &trace, string &str)
    {
        path.push_back(str);
        if (trace.count(str) == 0)
        {
            reverse(path.begin(), path.end());
            res.push_back(path);
            return;
        }
        for (auto word : trace[str])
            dfs(res, path, trace, word);
    }
};
```

### C
```cpp
class Solution
{
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string> &wordList)
    {

        vector<vector<string>> ans;

        unordered_set<string> dict(wordList.begin(), wordList.end());

        vector<string> p{beginWord};

        queue<vector<string>> paths;

        paths.push(p);

        unordered_set<string> words;

        int level = 1, minlength = INT_MAX;
        while (!paths.empty())
        {

            vector<string> t = paths.front();
            paths.pop();

            if (t.size() > level)
            {
                for (string s : words)
                    dict.erase(s);
                words.clear();
                level = t.size();
                if (level > minlength)
                    break;
            }

            string last = t.back();
            for (int i = 0; i < last.size(); ++i)
            {
                string newlast = last;

                for (char ch = 'a'; ch <= 'z'; ++ch)
                {
                    newlast[i] = ch;
                    if (!dict.count(newlast))
                        continue;

                    words.insert(newlast);
                    vector<string> nextpath = t;

                    nextpath.push_back(newlast);
                    if (newlast == endWord)
                    {
                        ans.push_back(nextpath);
                        minlength = level;
                    }
                    else
                    {
                        paths.push(nextpath);
                    }
                }
            }
        }
        return ans;
    }
};
```