Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, 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
.
注意题目意思是:给你一个单词,每次只能改变一个字母,改变后的单词要在dict中,最少经过过少次改变可以变成给定单词
本题通过广度搜索进行搜索
如
hit
经过一次改变 hot (其他单词都不在dict中,此时将hot从dict删除,这样可以避免hot->hot的循环)
经过第二次改变 dot lot (将dot和lot从dict中删除,dict={“dog”,”log”})
经过第三次改变 dog log
经过第四次改变 cog (找到,注意start算一次)
class Solution {
public:
int ladderLength(string start, string end, unordered_set<string> &dict) {
int res = ;
queue<string> que;
que.push(start);
bool flag = false;
while(!que.empty() && !flag){
int cnt = que.size();
res++;
while(cnt-->){
string a = que.front();que.pop();
if(a == end) {flag = true;break;}
for(int i = ; i < a.length();++ i){
string bk(a);
for(char j ='a' ; j <= 'z'; ++ j ){
bk[i] = j;
if(dict.find(bk)!=dict.end() && bk!=a){
que.push(bk);
dict.erase(bk);
}
}
}
}
}
if(!flag) return ;
else return res;
}
};