**一. 题目描述** Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that: • Only one letter can be changed at a time  • Each intermediate word must exist in the dictionary For example, Given: start = “hit”  end = “cog”  dict = [“hot”,”dot”,”dog”,”lot”,”log”] As one shortest transformation is ”hit” -> ”hot” -> ”dot” -> ”dog” -> ”cog”, return its length 5. Note: • Return 0 if there is no such transformation sequence.  • All words have the same length.  • All words contain only lowercase alphabetic characters. **二. 题目分析** 参考链接：[http://www.mamicode.com/info-detail-448603.html](http://www.mamicode.com/info-detail-448603.html) 可以将这道题看成是一个图的问题。我们将题目映射到图中，顶点是每个字符串，然后两个字符串如果相差一个字符则进行连边。我们的字符集只有小写字母，而且字符串的长度固定，假设是L。那么可以注意到每一个字符可以对应的边有25个（26个小写字母去掉自己），那么一个字符串可能存在的边是25*L条。接下来就是检查这些对应的字符串是否在字典内，就可以得到一个完整的图的结构。根据题目要求，等价于求这个图中一个顶点到另一个顶点的最短路径，我们一般用BFS广度优先。 这道题，我们只能用最简单的办法去做，每次改变单词的一个字母，然后逐渐搜索，这种求最短路径，树最小深度问题用BFS最合适。 和当前单词相邻的单词，就是和顶点共边的另一个顶点，是对当前单词改变一个字母且在字典内存在的单词。 找到一个单词的相邻单词，加入BFS队列后，我们要从字典内删除，因为不删除会造成类似hog->hot->hog这样的死循环。而且删除对求最短路径没有影响，因为我们第一次找到的单词肯定是最短路径，我们是层序遍历去搜索的，最早找到的一定是最短路径，即使后面的其他单词也能转换成它，路径肯定不会比当前的路径短。这道题仅要求求出最短路径长度，不需要求输出最短路径，所以可以删除这个单词。 BFS队列之间用空串”“来标示层与层的间隔，每次碰到层的结尾，遍历深度+1，进入下一层。 **三. 示例代码** ~~~ class Solution { public: int ladderLength(string start, string end, unordered_set<string> &dict) { if(start.size() == 0 || end.size() == 0) return 0; queue<string> wordQ; wordQ.push(start); wordQ.push(""); int path = 1; while(!wordQ.empty()) { string str = wordQ.front(); wordQ.pop(); if(str != "") { int len = str.size(); for(int i = 0; i < len; i++) { char tmp = str[i]; for(char c = 'a'; c <= 'z'; c++) { if(c == tmp) continue; str[i] = c; if(str == end) return path + 1; //如果改变后的单词等于end 返回path+1 if(dict.find(str) != dict.end()) { wordQ.push(str); dict.erase(str); //字典内删除这个词 防止反复走 } } str[i] = tmp; //重置回原来的单词 } } else if(!wordQ.empty()) { //到达当前层的结尾，并且不是最后一层的结尾 path++; wordQ.push(""); } } return 0; } }; ~~~