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.
关键字 "...find the length of shortest transformation sequence from beginWord to endWord..." 最短路径,用BFS解决:1.需要Queue来做BFS,2.hash table来避免重复。 BFS:起点是beginWord,边是变换成和当前word只差一个字母并且存在在字典里的词。 这道题要求出最短路径是多少(多少层),当用BFS遍历时,需要明确知道什么时候当前层结束,开始下一层,层数此时+1。最简单的做法是用两个queue来实现:queue1装当前层的节点,queue2装下一层节点,当queue1为空时,代表当前层节点遍历结束.
1 class Solution { 2 public: 3 int ladderLength(string beginWord, string endWord, vector& wordList) { 4 unordered_set dict(wordList.begin(),wordList.end()); //hashtable containing unvisited words 5 int length = 1; 6 queue queue1; //current level 7 queue queue2; //next level 8 queue1.push(beginWord); 9 10 //BFS11 while(!queue1.empty()){12 string currWord = queue1.front();13 if(currWord==endWord){ //equals endWord: find the transformation14 return length;15 }16 queue1.pop();17 18 //checking neighbors19 //1. each letter can be changed20 for(int i=0;i temp;44 queue2 = temp;45 }46 }47 48 return 0;49 }50 };