solution.md

# 单词接龙

<p>字典 <code>wordList</code> 中从单词 <code>beginWord</code><em> </em>和 <code>endWord</code> 的 <strong>转换序列 </strong>是一个按下述规格形成的序列：</p>

<ul>
	<li>序列中第一个单词是 <code>beginWord</code> 。</li>
	<li>序列中最后一个单词是 <code>endWord</code> 。</li>
	<li>每次转换只能改变一个字母。</li>
	<li>转换过程中的中间单词必须是字典 <code>wordList</code> 中的单词。</li>
</ul>

<p>给你两个单词<em> </em><code>beginWord</code><em> </em>和 <code>endWord</code> 和一个字典 <code>wordList</code> ，找到从 <code>beginWord</code> 到 <code>endWord</code> 的 <strong>最短转换序列</strong> 中的 <strong>单词数目</strong> 。如果不存在这样的转换序列，返回 0。</p>
 

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

<pre>
<strong>输入：</strong>beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
<strong>输出：</strong>5
<strong>解释：</strong>一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。
</pre>

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

<pre>
<strong>输入：</strong>beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
<strong>输出：</strong>0
<strong>解释：</strong>endWord "cog" 不在字典中，所以无法进行转换。</pre>

<p> </p>

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

<ul>
	<li><code>1 <= beginWord.length <= 10</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>

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

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;
```
### after

```cpp
int main()
{
    Solution sol;
    int res;
    string beginWord = "hit", endWord = "cog";
    vector<string> wordList = {"hot", "dot", "dog", "lot", "log", "cog"};
    res = sol.ladderLength(beginWord, endWord, wordList);
    cout << res;
    return 0;
}
```

## 答案

```cpp
class Solution
{
public:
    int ladderLength(string beginWord, string endWord, vector<string> &wordList)
    {
        unordered_set<string> word;
        for (auto s : wordList)
        {
            word.insert(s);
        }
        if (word.find(endWord) == word.end())
        {
            return 0;
        }
        queue<string> que;
        que.push(beginWord);
        unordered_set<string> visited;
        visited.insert(beginWord);
        int num = 1;
        while (!que.empty())
        {
            int m = que.size();
            for (int i = 0; i < m; i++)
            {
                string str = que.front();
                que.pop();
                if (str == endWord)
                {
                    return num;
                }
                for (int j = 0; j < str.size(); j++)
                {
                    string ss = str;
                    for (int k = 0; k < 26; k++)
                    {
                        char c = k + 'a';
                        if (c != str[j])
                        {
                            ss[j] = c;
                        }
                        if (visited.find(ss) == visited.end())
                        {
                            visited.insert(ss);
                            que.push(ss);
                        }
                    }
                }
            }
            num++;
        }
        return 0;
    }
};
```
## 选项

### A
```cpp
class Solution
{
public:
    int ladderLength(string beginWord, string endWord, vector<string> &wordList)
    {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        if (!wordSet.count(endWord))
            return 0;

        unordered_map<string, int> pathCount{{{beginWord, 1}}};
        queue<string> q{{beginWord}};
        while (!q.empty())
        {
            string word = q.front();
            q.pop();
            for (int i = 0; i < word.size(); i++)
            {
                string newWord = word;
                for (char c = 'a'; c <= 'z'; c++)
                {
                    newWord[i] = c;
                    if (wordSet.count(newWord) && newWord == endWord)
                        return pathCount[word] + 1;
                    if (wordSet.count(newWord) && !pathCount.count(newWord))
                    {
                        pathCount[newWord] = pathCount[word] + 1;
                        q.push(newWord);
                    }
                }
            }
        }
        return 0;
    }
};
```

### B
```cpp
class Solution
{
public:
    int ladderLength(string beginWord, string endWord, vector<string> &wordList)
    {
        queue<string> q;
        map<string, int> m1;
        map<string, int> re;
        int n = wordList.size();
        for (int i = 0; i < n; i++)
            m1[wordList[i]] = 1;
        re[beginWord] = 1;
        q.push(beginWord);
        while ((!q.empty()) && m1.size())
        {
            string now = q.front();
            q.pop();
            int num = re[now];
            int llen = now.size();
            for (int i = 0; i < llen; i++)
            {
                string temp = now;
                for (char c = 'a'; c <= 'z'; c++)
                {
                    if (temp[i] == c)
                        continue;
                    else
                        temp[i] = c;
                    if (m1.find(temp) != m1.end())
                    {
                        if (temp == endWord)
                            return num + 1;
                        q.push(temp);
                        re[temp] = num + 1;
                        m1.erase(temp);
                    }
                }
            }
        }
        return 0;
    }
};
```

### C
```cpp
class Solution
{
public:
    int ladderLength(string beginWord, string endWord, vector<string> &wordList)
    {
        unordered_set<string> set(wordList.begin(), wordList.end());
        if (!set.count(endWord))
            return 0;
        queue<pair<string, int>> q;
        q.push({beginWord, 1});
        while (!q.empty())
        {
            string cur = q.front().first;
            int step = q.front().second;
            q.pop();
            if (cur == endWord)
                return step;

            for (int i = 0; i < cur.size(); ++i)
            {
                char ch = cur[i];

                for (char c = 'a'; c <= 'z'; ++c)
                {
                    if (c == ch)
                        continue;
                    cur[i] = c;
                    if (set.count(cur))
                    {
                        q.push({cur, 1 + step});
                        set.erase(cur);
                    }
                }
                cur[i] = ch;
            }
        }
        return 0;
    }
};
```