Description:
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.
Example:
Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Link:
https://leetcode.com/problems/word-ladder/#/description
解題方法：
用哈希表把WordList中的單詞記下來嗅钻，然后用bfs毡惜。
transform的方法是根據(jù)現(xiàn)有單詞的每個(gè)字母，用26個(gè)字母輪流去替換证膨，如果替換出來的結(jié)果在哈希表中則代表可以走一步。每走完一步刪除哈希表中對(duì)應(yīng)的單詞考廉，這樣可以保證不會(huì)走重復(fù)的步驟上忍。
Tips:
用unordered_map在LeetCode里面不能AC，所以需要換成unordered_set酱吝。這樣占用內(nèi)存更小也殖。
完整代碼：
int ladderLength(string beginWord, string endWord, vector<string>& wordList)
{
unordered_set <string> hash;
for(auto a: wordList)
hash.insert(a);
queue<string> Q;
Q.push(beginWord);
int cnt = 0;
while(!Q.empty())
{
int len = Q.size();
cnt++;
for(int i = 0; i < len; i++)
{
string curr = Q.front();
Q.pop();
if(curr == endWord)
return cnt;
for(int j = 0; j < curr.size(); j++)
{
for(int k = 0; k < 26; k++)
{
string temp = curr;
temp[j] = 'a' + k;
if(hash.find(temp) != hash.end())
{
hash.erase(temp);
Q.push(temp);
}
}
}
}
}
return 0;
}
