字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：
- 每一对相邻的单词只差一个字母。
- 对于
1 <= i <= k时，每个si都在wordList中。注意，beginWord不需要在wordList中。 sk == endWord
给你两个单词 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中的所有字符串 互不相同
解题思路：边权为一的最短路问题 -> bfs解决
这道题其实和 433. 最小基因变化 是类似的，只不过细节上有些不同罢了，因为思想是类似的，所以为什么可以转化为边权为一的最短路问题，这里就不再赘述了，具体可以参考上一道题的笔记！
我们主要来讲一下这道题的不同之处：这道题没有明确指出转化字符有哪些，而上一道是直接给出一个转化字符序列的。
这就导致了会出现这种时间复杂度比较高的思路，也是我一开始想到的思路：遍历 wordList 中所有字符串，如果 wordList[i] 没出现过，并且和 front 相差一个字符，才进行处理。虽然看起来没问题，但是每次去判断是否和 front 相差一个字符，我们要单独写一个带有循环的函数，又放在了遍历 wordList 中所有字符串的循环中，此时相当于就一个节点判断的时间复杂度来说，就达到了 O(n^2)，虽然在这道题是跑的过去的，但是时间复杂度是不容乐观的：
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> used; // 存储已经枚举过的单词，方便去重
unordered_set<string> word_hash(wordList.begin(), wordList.end()); // 存储wordList中的单词，便于快速索引
// 先进行边界处理
if(word_hash.count(endWord) == 0)
return 0;
queue<string> bfs;
bfs.push(beginWord);
int step = 1;
while(!bfs.empty())
{
step++; // 进入一层广度就让step累加
int size = bfs.size();
while(size--)
{
string front = bfs.front();
bfs.pop();
// 遍历wordList中所有字符串
for(int i = 0; i < wordList.size(); ++i)
{
// 如果wordList[i]没出现过，并且和front相差一个字符，才进行处理
// 时间复杂度高的原因是one_char()函数也是一个循环
if(used.count(wordList[i]) == 0 && one_char(front, wordList[i]) == true)
{
// 如果就是结果字符串，则直接返回
if(endWord == wordList[i])
return step;
// 不是的话则加入队列中作为中间序列
bfs.push(wordList[i]);
used.insert(wordList[i]);
}
}
}
}
return 0;
}
// 判断两个字符串是否相差一个字符
bool one_char(string& s1, string& s2)
{
int count = 0;
for(int i = 0; i < s1.size(); ++i)
{
if(s1[i] != s2[i])
{
if(count == 0)
count++;
else
return false;
}
}
return count == 0 ? false : true;
}
}; 所以后面改变了一下思路，仔细一想是没有利用上 word_hash 这个哈希表来快速索引，又因为题目说 beginWord、endWord 和 wordList[i] 由小写英文字母组成，那么我们可以像 433. 最小基因变化 这道题一样，修改字符串上的字符，然后根据 word_hash 来快速判断是否存在修改后的字符串，这样子效率是非常高的。而修改的字符，就在小写字母 a~z 范围内，这个并不难理解！
所以修改完的代码如下所示，只需要看循环那部分代码即可：
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> used; // 存储已经枚举过的单词，方便去重
unordered_set<string> word_hash(wordList.begin(), wordList.end()); // 存储wordList中的单词，便于快速索引
// 先进行边界处理
if(word_hash.count(endWord) == 0)
return 0;
queue<string> bfs;
bfs.push(beginWord);
int step = 1;
while(!bfs.empty())
{
step++; // 进入一层广度就让step累加
int size = bfs.size();
while(size--)
{
string front = bfs.front();
bfs.pop();
// 不是遍历wordList，而是遍历字符串front的长度，进行字符的修改
for(int i = 0; i < front.size(); ++i)
{
string tmp = front; // 细节：因为不能修改front，所以用临时变量tmp
for(char c = 'a'; c <= 'z'; ++c)
{
tmp[i] = c; // 修改字符串中的字符
// 使用两个哈希表进行快速索引判断，思路和上面是一样的！
if(used.count(tmp) == 0 && word_hash.count(tmp) != 0)
{
// 如果就是结果字符串，则直接返回
if(endWord == tmp)
return step;
// 不是的话则加入队列中作为中间序列
bfs.push(tmp);
used.insert(tmp);
}
}
}
}
}
return 0;
}
};可以看到两个代码跑出来的时间复杂度级别是天差地别的，超过了十倍！
