给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
- 每次转换只能改变一个字母。
- 转换过程中的中间单词必须是字典中的单词。
说明:
- 如果不存在这样的转换序列，返回 0。
- 所有单词具有相同的长度。
- 所有单词只由小写字母组成。
- 字典中不存在重复的单词。
- 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 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" 不在字典中，所以无法进行转换。
解法一：单向bfs，用时有些多。
class Solution {
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {//边界条件if(wordList.empty()) return 0;if(find(wordList.begin(), wordList.end(), endWord) == wordList.end()) return 0;//转换的步长,把自己给算上了，所以要从1开始算int step = 1;//记录wordList中的哪些单词已经被访问过vector<int> visit(wordList.size(), 0);//bfsqueue<string> que;que.push(beginWord);while(!que.empty()) {//进入下一层，step++step++;//队列长度int length = que.size();while(length--) {string tmp = que.front();que.pop();for(int i = 0; i < wordList.size(); ++i) {if(visit[i] == 0) {//记录字母不同的个数int diff = 0;for(int j = 0; j < tmp.size(); ++j) {if(tmp[j] != wordList[i][j]) ++diff;}if(diff == 1) {if(wordList[i] == endWord) return step;visit[i] = 1;que.push(wordList[i]);}}}}}return 0;}
};
解法二：双向bfs（看的我人傻了）
class Solution {
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {//建立字典库unordered_set<string> dict(wordList.begin(),wordList.end());//边界条件if(dict.find(endWord) == dict.end()) return 0 ;//建立双向搜索过程，一个从顶端往下搜索，一个从底端往上搜索，还需要记录访问过的//并且建立一个tmp，用来保证每次搜索的都是begin和end中长度最小的unordered_set<string> beginSet, endSet, tmp, visit;//初始化开始集合和结束集合beginSet.insert(beginWord);endSet.insert(endWord);int step = 1;//开始双向bfswhile(!beginSet.empty() && !endSet.empty()) {//取出begin和end中较小的来搜索if(beginSet.size() > endSet.size()) {tmp = beginSet;beginSet = endSet;endSet = tmp;}tmp.clear();for(auto word : beginSet) {for(int i = 0; i < word.size(); ++i) {char old = word[i];//对搜索集合中的单词中的每个字母都进行‘a’到‘z’的替换//替换后查询是否在结果中，在即返回，不在但在词库中，则进入下一轮搜索。for(char c = 'a'; c <= 'z'; ++c) {if(old == c) continue;word[i] = c;if(endSet.find(word) != endSet.end()) return step + 1;if(visit.find(word) == visit.end() && dict.find(word) != dict.end()) {tmp.insert(word);visit.insert(word);}}word[i] = old;}}beginSet = tmp;++step;}return 0;}
};