Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
- Only one letter can be changed at a time.
- Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
Note:
- Return 0 if there is no such transformation sequence.
- All words have the same length.
- All words contain only lowercase alphabetic characters.
- You may assume no duplicates in the word list.
- You may assume beginWord and endWord are non-empty and are not the same.
Example 1:
Input:beginWord = "hit",endWord = "cog",wordList = ["hot","dot","dog","lot","log","cog"]Output: 5Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",return its length 5.
Example 2:
Input:beginWord = "hit"endWord = "cog"wordList = ["hot","dot","dog","lot","log"]Output: 0Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
解题思路：
将题目映射到图中，顶点是每个字符串，然后两个字符串如果相差一个字符则进行连边。根据题目要求，等价于求这个图中一个顶点到另一个顶点的最短路径，我们一般用广度优先。
每次改变单词的一个字母，然后逐渐搜索，这种求最短路径，树最小深度问题用BFS最合适。
- 和当前单词相邻的单词，就是和顶点共边的另一个顶点，是对当前单词改变一个字母且在字典内存在的单词
- 找到一个单词的相邻单词，加入BFS队列后，我们要从字典内删除，因为不删除会造成类似hog->hot->hog这样的死循环。而且删除对求最短路径没有影响，因为我们第一次找到的单词肯定是最短路径，我们是层序遍历去搜索的，最早找到的一定是最短路径，即使后面的其他单词也能转换成它，路径肯定不会比当前的路径短。这道题仅要求求出最短路径长度，不需要求输出最短路径，所以可以删除这个单词。
- BFS队列之间用空串“”来标示层与层的间隔，每次碰到层的结尾，遍历深度+1，进入下一层。
class Solution { public: int ladderLength(string beginWord, string endWord, vector & w) { unordered_set wordList(w.begin(),w.end());//转换为set便于操作 queue > q; q.push(make_pair(beginWord,1)); //在单词列表中查找是否有开头的单词，有的话删掉 auto it=wordList.find(beginWord); if(it!=wordList.end()) wordList.erase(it); while(!q.empty()) { auto t=q.front(); q.pop(); if(t.first==endWord) return t.second; //遍历单词中的每个字符 for(int i=0;i