欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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;
    }
};
相关标签: word