题目描述
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.
Example1:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: 5 Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.
Example2:
Input: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"] Output: 0 Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
解题思路
- BFS搜索
- 题意是，由一个单词开始，每次只能变化一个字母，这个变化后的字符串需要在集合里面，然后需要经过多少步才能变换到最后的位置？
- 跟走迷宫类似，只是把走迷宫问题的4个方向转变成了26个方向
- 为了提到字典的查找效率，我们使用HashSet保存所有的单词。
- 然后我们需要一个HashMap，来建立某条路径结尾单词和该路径长度之间的映射，并把起始单词映射为1。
- 既然是BFS，我们需要一个队列queue，把起始单词排入队列中，开始队列的循环，取出队首词，然后对其每个位置上的字符，用26个字母进行替换，如果此时和结尾单词相同了，就可以返回取出词在哈希表中的值加一。
- 如果替换词在字典中存在但在哈希表中不存在，则将替换词排入队列中，并在哈希表中的值映射为之前取出词加一。
- 如果循环完成则返回0
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> wordSet(wordList.begin(), wordList.end());
if(!wordSet.count(endWord)){
return 0;
}
unordered_map<string, int> mmap;
mmap[beginWord] = 1;
queue<string> q;
q.push(beginWord);
while(!q.empty()){
string word = q.front();
q.pop();
for(int i = 0; i < word.size(); i++){
string newWord = word;
for(int j = 0; j < 26; j++){
newWord[i] = j + 'a';
if(wordSet.count(newWord) && newWord == endWord){
return mmap[word] + 1;
}
if(wordSet.count(newWord) && !mmap.count(newWord)){
mmap[newWord] = mmap[word] + 1;
q.push(newWord);
}
}
}
}
return 0;
}
};
