Question :
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
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:
For Example:
Graph Array = [
h i t
h o t
d o t
d o g
l o t
l o g
c o g
]
Anwser 1 :
class Solution {
public:
int ladderLength(string start, string end, unordered_set<string> &dict) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(start == end) return 0; // shortest length
queue <pair<string, int>> Q;
map<string, bool> hmap;
vector<string> vec;
Q.push(make_pair(start, 1)); // start word
while(!Q.empty()){
pair<string, int> node = Q.front();
string word = node.first;
int level = node.second;
if(word == end){
break;
}
Q.pop();
vec.clear();
getWords(vec, word, hmap, dict);
int len = vec.size();
for(int i = 0; i < len; ++i){
Q.push(make_pair(vec[i], level + 1));
}
}
if(Q.empty()) {
return 0;
} else {
return Q.front().second;
}
}
void getWords(vector<string> &vec, string start, map<string, bool> &hmap, const unordered_set<string> &dict){
int n = start.size();
for(int i = 0; i < n; ++i)
{
string temp(start);
for(int j = 0; j < 26; ++j)
{
temp[i] = j + 'a'; // a - z
if(temp != start && dict.find(temp) != dict.end() && hmap.find(temp) == hmap.end())
{
hmap.insert(make_pair(temp, false));
vec.push_back(temp);
}
}
}
}
};
Anwser 2 :
class Solution {
public:
int ladderLength(string start, string end, unordered_set<string> &dict) {
unordered_set<string> Set;
queue<string> Q;
int curLevel = 1;
int curLevelNum = 1;
int nextLevelNum = 0;
Set.insert(start);
Q.push(start);
while (!Q.empty())
{
string cur = Q.front();
Q.pop();
--curLevelNum;
for (unordered_set<string>::iterator it = dict.begin(); it != dict.end(); ++it)
{
string temp = *it;
if (canChange(temp, cur) && Set.find(temp) == Set.end())
{
Q.push(temp);
Set.insert(temp);
++nextLevelNum;
}
}
if (canChange(cur, end)) return curLevel + 1;
if (curLevelNum == 0)
{
++curLevel;
curLevelNum = nextLevelNum;
nextLevelNum = 0;
}
}
return 0;
}
bool canChange(string a, string b)
{
if (a.size() != b.size())
return false;
int count = 0;
for (int i = 0; i < a.size(); ++i)
{
if (a[i] != b[i])
{
if (count == 1) return false; // more than 1 letters diff, return
++count;
}
}
return count == 1; // only one letter diff
}
};
参考推荐: