# 单词接龙
字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：
- 序列中第一个单词是
beginWord 。
- 序列中最后一个单词是
endWord 。
- 每次转换只能改变一个字母。
- 转换过程中的中间单词必须是字典
wordList 中的单词。
给你两个单词 beginWord 和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。
示例 1：
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。
示例 2：
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中，所以无法进行转换。
提示：
1 <= beginWord.length <= 10endWord.length == beginWord.length1 <= wordList.length <= 5000wordList[i].length == beginWord.lengthbeginWord、endWord 和 wordList[i] 由小写英文字母组成beginWord != endWordwordList 中的所有字符串 互不相同
以下错误的选项是？
## aop
### before
```cpp
#include
using namespace std;
```
### after
```cpp
int main()
{
Solution sol;
int res;
string beginWord = "hit", endWord = "cog";
vector 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 &wordList)
{
unordered_set word;
for (auto s : wordList)
{
word.insert(s);
}
if (word.find(endWord) == word.end())
{
return 0;
}
queue que;
que.push(beginWord);
unordered_set 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 &wordList)
{
unordered_set wordSet(wordList.begin(), wordList.end());
if (!wordSet.count(endWord))
return 0;
unordered_map pathCount{{{beginWord, 1}}};
queue 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 &wordList)
{
queue q;
map m1;
map 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 &wordList)
{
unordered_set set(wordList.begin(), wordList.end());
if (!set.count(endWord))
return 0;
queue> 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;
}
};
```