给定两个单词（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” 不在字典中，所以无法进行转换。 通过次数46,730提交次数109,825
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/word-ladder 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路： 这是一道图的广度优先搜索，将字符能够相互转化视为图中两个节点所相连的边，此时通过以beginWord出发进行广度优先搜索遍历，期间记录遍历到每个位置的步数，可以获得最短的长度。难点有三个，一是将字符集抽象为图并选择合适的数据结构进行图的构建；二是此题目可以通过双向bfs来优化宽度优先搜索的时间复杂度；三是广度优先遍历过程中的已访问的设置，和搜索结束的条件设置。下面分别说明三个难点的解决方式： 1. 对于图的构建，可以使用map，key值中存储字符串，而value中存储为与该字符串相连即能够以题目条件相互转化的字符串的vector，亦即是以邻接表的方式构建图。因此需要实现一个判断是否相连的函数，之后双层遍历wordlist中的所有字符串，构建所有字符串的邻接表即可。需要注意的是，需要将beginword加入wordlist。 2. 双向bfs应用的场景是知道遍历要找的路径的起点和终点，分别从两边向中间进行遍历，当两边访问到相同的节点的时候，即说明找到了一条最短的路径，记录此时的长度即可。相对于单向的bfs，双向bfs优化了搜索空间，降低了时间复杂度。在实现的时候，需要设置两个遍历所需的队列，同时，为了减少遍历结束的条件判断的复杂度，需要一定的规则。本题中，默认先对一个队列进行中的队头元素进行bfs，将它的所有相邻接点入队并修改访问记录数组，同时，在每个元素入队的时候在另一个访问数组中查找这个元素，如果找到则说明满足退出条件，记录此时的结果，没有找到的话修改访问记录数组，注意：访问记录数组中需要同时记录到这个节点的步数。之后对另一个队头元素做相同的操作直至遍历结束或者找到结果。 3. 在本题中，无论是双向bfs和单向bfs都需要特别的设置访问数组，因为需要记录遍历到当前节点所走的步数，以便返回最后的结果。而对于本题的双向bfs，需要频繁的进行元素的查找。因此使用 stl：：set（pair<string，int>）作为访问数组，而搜索结束的条件在2中已经详细说明。 ps：我的解法里，双向bfs仅仅快了400ms，大概20%,大概是太垃圾了吧，同时，写代码的时候要注意细节，在判断队列是否为空的时候切记要检查叹号是不是该用，特别是要同时判断两个队列的时候，少打一个叹号找了半小时。淦！
class Solution { public: int ladderLength(string beginWord, string endWord, vector<string>& wordList) { queue<pair<string,int>> q1; queue<pair<string,int>> q2; unordered_map<string,int> fv; unordered_map<string,int> bv; unordered_map<string,vector<string>> graph; constructGraph(wordList,beginWord,graph); q1.push(pair<string,int>(beginWord,1)); q2.push(pair<string,int>(endWord,1)); fv[beginWord] = 1; bv[endWord] = 1; while(!q1.empty()&&!q2.empty()) { int ret = visitWordNode(q1,fv,bv,graph); if(ret>-1)return ret; ret = visitWordNode(q2,bv,fv,graph); if(ret>-1)return ret; //cout<<ret<<endl; } return 0; } int visitWordNode(queue<pair<string,int>>& Q,unordered_map<string,int>& visit,unordered_map<string,int>& anovisit, unordered_map<string,vector<string>>& graph) { string tempStr = Q.front().first; int step = Q.front().second; Q.pop(); for(auto str : graph[tempStr]) { if(anovisit.find(str)!=anovisit.end()) { return step+anovisit[str]; } if(visit.find(str)==visit.end()) { Q.push(pair<string,int>(str,step+1)); visit[str] = step+1; } } return -1; } bool isConnect(string &a,string &b) { int len = a.size(); int count = 0; for(int i = 0;i<len;i++) { if(a[i]!=b[i]) { count++; } } if(count==1)return true; return false; } void constructGraph(vector<string>& wordstring,string &beginWord, unordered_map<string,vector<string>> &graph) { wordstring.push_back(beginWord); for(int i = 0;i<wordstring.size();i++) { graph[wordstring[i]] = vector<string>(); } for(int i = 0;i<wordstring.size();i++) { for(int j = i+1;j<wordstring.size();j++) { if(isConnect(wordstring[i],wordstring[j])) { graph[wordstring[i]].push_back(wordstring[j]); graph[wordstring[j]].push_back(wordstring[i]); } } } } };