Given two words (beginWord and endWord), and a dictionary, find the length of shortest transformation sequence from beginWord to endWord, such that:
- Only one letter can be changed at a time
- Each intermediate word must exist in the dictionary
For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Note:
- Return 0 if there is no such transformation sequence.
- All words have the same length.
- All words contain only lowercase alphabetic characters.
每次只能改变一个字符，求最短路径。
开始想法为列出二维矩阵，找出变化一次，变化两次，知道变化为end，从而求最短路径。然而发现需要内存过多，同时超时。
改为采用BFS，这样首先找到的肯定是最短路径。但是同样超时。看到网上都是用java实现的，不知道是什么问题。
class Solution {
private:
int isOneDiff(string beginWord, string endWord)
{
int n=beginWord.size();
int m=endWord.size();
if(n!=m) return -;
int count=;
for(int i=;i<n;i++)
{
if(beginWord[i]!=endWord[i])
count++;
}
if(count>) return -;
return count;
}
public:
int ladderLength(string beginWord, string endWord, unordered_set<string>& wordDict) {
int n=wordDict.size();
if(beginWord.empty()||endWord.empty()||n<||beginWord.size()!=endWord.size()||isOneDiff(beginWord,endWord)==)
return ;
if(isOneDiff(beginWord,endWord)==)
return ;
if((wordDict.find(beginWord)!=wordDict.end())&&(wordDict.find(endWord)!=wordDict.end())&&(n==))
return ;
queue<string> q;
map<string,int> wordmap;
int wordlength=beginWord.size();
int count=;
q.push(beginWord);
wordmap.insert(pair<string,int>(beginWord,count));
while(!q.empty())
{
string tmpword=q.front();
count=wordmap[tmpword];
q.pop();
for(int i=;i<wordlength;i++)
{
for(char j='a';j<='z';j++)
{
if(j==tmpword[i]) continue;
tmpword[i]=j;
if(tmpword==endWord) return count+;
if(wordDict.find(tmpword)!=wordDict.end())
{
q.push(tmpword);
wordmap.insert(pair<string,int>(tmpword,count+));
}
}
}
}
return ;
}
};