心情：最近打代码也是非常不在状态啊！花了差不多半天的时间写这道题。
题目描述：
给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
说明:
如果不存在这样的转换序列，返回一个空列表。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 1:
输入:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
输出:
[
[“hit”,“hot”,“dot”,“dog”,“cog”],
[“hit”,“hot”,“lot”,“log”,“cog”]
]
示例 2:
输入:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,“dot”,“dog”,“lot”,“log”]
输出: []
解释: endWord “cog” 不在字典中，所以不存在符合要求的转换序列。
方法一：我当时想的第一个方法暴力，很正常，超时
方法二：既然方法一超时，我于是用map保存了通过一步能转换的下一个字符串（自言自语）
方法三：BFS
关于这里的BFS，我前期一直以为是树意义上的BFS，所以我当时想的方法是：首先，找出所有与某一个字符串能相邻转化的字符串，保存在map<string,set< string >>里面，之后再从beginWord开始循环，用BFS开始循环beginWord的set里面的Word，然后用一个set来判断某个Word是否被访问了，访问了就删除。
然后提交，依然超时，为啥？
相当于是你BFS循环的时候访问了所有Word的set里面的Word，这明显是没必要的。
说道理，我好像没怎么懂这个原理，但是我觉得这种题可以归结为图上的一个点到另外一个点的题目，且找的是最短的，那么方法就是找当前点可能的邻接点，然后这个邻接点就不能成为其他点的邻接点了（因为你明明可以直接从当前点到它，为啥要经过之后的点再到它呢？），最后找到最终点，就是最短路径。
代码如下：
class Solution {
public:
void dfs(string &curWord,string &endWord,unordered_map<string,unordered_set<string>> &nextWord,vector<string> &vec,vector<vector<string>> &result){
if(curWord == endWord){
result.push_back(vec);
}else{
for(auto w:nextWord[curWord]){
vec.push_back(w);
dfs(w,endWord,nextWord,vec,result);
vec.pop_back();
}
}
}
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> words(wordList.begin(),wordList.end());
if(words.size() == 0) return {};
vector<string> q;
unordered_map<string,unordered_set<string>> nextWord;
q.push_back(beginWord);
while(!q.empty()){
for(string &str:q){
words.erase(str);
}
vector<string> tmp;
while(!q.empty()){
string w = q[q.size()-1];
q.pop_back();
for(int j = 0;j < w.size();j++){
string str = w;
for(char c = 'a';c <= 'z';c++){
str[j] = c;
if(words.find(str) != words.end()){
nextWord[w].insert(str);
tmp.push_back(str);
}
}
}
}
q = tmp;
}
vector<vector<string>> result;
vector<string> vec;
vec.push_back(beginWord);
dfs(beginWord,endWord,nextWord,vec,result);
return result;
}
};
今日份的收获：
set和unordered_set区别：
std::set 是关联容器，含有 Key 类型对象的已排序集。用比较函数 Compare 进行排序。搜索、移除和插入拥有对数复杂度。 set 通常以红黑树实现，红黑树具有自动排序的功能，因此set内部所有的数据，在任何时候，都是有序的。
std::unordered_set 是含有 Key 类型唯一对象集合的关联容器，依赖于哈希表。搜索、插入和移除拥有平均常数时间复杂度。在内部，元素并不以任何特别顺序排序，而是组织进桶中，元素被放进哪个桶完全依赖其值的哈希。允许对单独元素的快速访问，因为一旦哈希，就能够准确指代元素被放入的桶。不可修改容器元素（即使通过非 const 迭代器），因为修改可能更改元素的哈希，并破坏容器。代价是消耗比较多的内存，无自动排序功能。底层实现上，使用一个下标范围比较大的数组来存储元素，形成很多的桶，利用hash函数对key进行映射到不同区域进行保存。
下面几种情况一般使用set：
需要有序的数据(元素不同)。
需要按顺序打印/访问数据。
需要元素的前任或后继。
下面几种情况一般使用unordered_set：
需要保留一组不同的元素，不需要排序。
需要访问单个元素，不要遍历。
搜索元素。
转载：https://blog.csdn.net/cirol1997/article/details/102592572