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.
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.
给定两个单词beginword和endword、一个词典,单词和词典中的词同样长,问:每次改变一个单词,能否在每次改变后的单词都在词典中的情况下,由beginword转化为endword。
图的广度优先搜索。
将每个单词视为一个节点,它的邻居节点为只有一个字母之差的单词,按照广度优先搜索的顺序将这些单词放入一个队列里。
取队列头单词"word",每次改变word中一个字母,去dict中找有没有只差一个字母的单词,有的话放入队列中。要注意取完word后要在dict中删除word,以免重复。
需要注意的一点是unordered_set的使用,它是一个集合,因此不能插入相同的元素。
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> dict(wordList.begin(), wordList.end());
queue<string> todo;
todo.push(beginWord);
int ladder = 1;
while(!todo.empty()){
int n = todo.size();
for(int x=0; x<n; x++){
string word = todo.front();
todo.pop();
if(word == endWord) return ladder;
dict.erase(word);
for(int i=0; i<word.size(); i++){
char temp = word[i];
for(int letter=0; letter<26; letter++){
word[i] = 'a' + letter;
if(dict.find(word) != dict.end()){
todo.push(word);
}
}
word[i] = temp;
}
}
ladder++;
}
return 0;
}