思路：
1.如果采用回溯法来的话会超时；
2.这里采用构造图和广度优先遍历结合来实现；首先要构造图，需要将每个字符串对应一个数字id，然后边的构造使用矩阵来实现，这里采用将每一个字符串的id连接每个将该字符串的其中一个字符改为未知字符的字符串的id；如：
对于单词 hit，我们创建三个虚拟节点 *it、h*t、hi*，这三个点都与hit有连接边；
以此来判断一个字符串改变一个字符能够到达的点
在广度优先遍历中，如果能够找到一条到达endid的路径，那么该路径就是最短路径。
原题链接：https://leetcode.cn/problems/word-ladder/?favorite=2ckc81c
1.题目如下：
字典 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 <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord、endWord 和 wordList[i] 由小写英文字母组成
beginWord != endWord
wordList 中的所有字符串 互不相同
2.代码如下：
class Solution {
public:
//思路一：使用广度优先遍历BFS；
/*
遍历所有可能的路径，只要有路径，那就一定是最短路径；
同时需要标记每个节点是否被遍历过防止无限重复遍历；可能会超时
*/
//思路二：构造图+广度优先遍历
/*
将每个字符串转化成节点，并构造同其他节点的边
*/
int id=0;
//创建一个从字符串到id的映射表
unordered_map<string,int> mapTemp;
//矩阵用来存储每个结点的id能到达的边
vector<vector<int>> border;
void addWord(string& word) {
if (!mapTemp.count(word)) {
mapTemp[word] = id++;
border.emplace_back();
}
}
void addEdge(string& word) {
addWord(word);
// 原字符的id
int id1 = mapTemp[word];
//将每个字符都逐一变成'*'再放入字典，并构造边界
//对于单词 hit，我们创建三个虚拟节点 *it、h*t、hi*，这三个点都与hit有连接边
//让 hit 向这三个虚拟节点分别在矩阵中的id连一条边即可
for (char& it : word) {
char tmp = it;
it = '*';
// 将*it、h*t、hi*、的id添加进map
addWord(word);
// *it、h*t、hi*、的id与原id建立连接
int id2 =mapTemp[word];
border[id1].push_back(id2);
border[id2].push_back(id1);
it = tmp;
}
}
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
// 如果该字符串不存在，返回0
if(find(wordList.begin(),wordList.end(),endWord)==wordList.end()){
return 0;
}
// 将每个单词的id及对应边添加进矩阵中
for (string& word : wordList) {
addEdge(word);
}
addEdge(beginWord);
// 如果没有该字符串，返回0
if (!mapTemp.count(endWord)) {
return 0;
}
vector<int> dis(id, INT_MAX);
// 开始id和结尾id
int beginId = mapTemp[beginWord], endId = mapTemp[endWord];
//dis数据记录的是beginid到其他id的距离
dis[beginId] = 0;
//队列存储,广度优先遍历
queue<int> que;
//从开始单词的id开始，遍历所有边
que.push(beginId);
//广度优先遍历
while (!que.empty()) {
int x = que.front();
que.pop();
if(x==endId) {
//因为我们使用的是虚拟节点，所以距离要/2；因为每一次遍历，无向边都会导致dis[id]加两次
//得到的是最短距离
return dis[endId]/2+1;
}
//遍历所有边
for(int& it:border[x]) {
if(dis[it] == INT_MAX){
dis[it] = dis[x] + 1;
que.push(it);
}
}
}
return 0;
}
};
