Word Ladder
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
Given:
start =
end =
dict =
As one shortest transformation is
return its length
Note:
*/- Only one letter can be changed at a time
- Each intermediate word must exist in the dictionary
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.
class Solution {
public:
bool oneStep(string src, string des){
if(src.length() != des.length()) return false;
int difference = 0;
for(int i=0; i<src.length(); i++){
if(src[i]!=des[i]){
difference++;
if(difference>1) return false;
}
}
if (difference==0) return false;
else return true;
}
int ladderLength(string start, string end, unordered_set<string> &dict) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<string> inter;
inter.push_back(start);
dict.erase(start);
int size = inter.size();
int result = 1;
int i;
unordered_set<string>::iterator it;
while(!inter.empty()){
for(i=0; i<size; i++){
if(oneStep(inter[i], end)){
result++;
return result;
}
it = dict.begin();
while(it!=dict.end()){
if(oneStep(inter[i],*it)){
inter.push_back(*it);
it = dict.erase(it);
}
else{
it++;
}
}
}
result++;
inter.erase(inter.begin(), inter.begin()+size);
size = inter.size();
}
return 0;
}
};
No comments:
Post a Comment