Word Ladder
程序员文章站
2022-04-09 16:45:31
...
题目描述:
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.
For 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.
分析:一道显而易见的BFS题目,使用BFS即可。
代码如下:
class Solution {
public:
struct data{
int x;
string y;
};
bool check(string a,string b){
int num=0;
if(a.size()==b.size()){
for(int i=0;i<b.size();i++){
if(a[i]!=b[i])
num++;
}
}
return num==1;
}
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
queue<data>temp;
int len=wordList.size();
vector<int>vis(len,0);
data t;
t.x=1;
t.y=beginWord;
temp.push(t);
while(!temp.empty()){
data p=temp.front();
temp.pop();
if(p.y==endWord){
return p.x;
}
for(int i=0;i<len;i++){
if(!vis[i]&&check(p.y,wordList[i])){
vis[i]=1;
data k;
k.x=p.x+1;
k.y=wordList[i];
temp.push(k);
}
}
}
return 0;
}
};
上一篇: Qt操作Word文档
下一篇: three.js浏览全景图的代码