[题目 LeetCode 127] (https://leetcode.com/problems/word-ladder/description/)
题解：
BFS
struct Node
{
string word;
int dis;
Node(){}
Node(string word,int dis)
{
this->word = word;
this->dis = dis;
}
};
class Solution {
public:
int vis[100005];
queue<Node> q;
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
q.push(Node(beginWord,1));
int l = wordList.size();
int tag=0;
memset(vis,0,sizeof(vis));
for(int i=0;i<l;i++)
{
if(endWord==wordList[i])
{
tag=1;
}
}
if(tag==0)
return 0;
int ans = 0;
while(!q.empty())
{
Node term = q.front();
q.pop();
if(term.word == endWord)
{
ans = term.dis;
break;
}
for(int i=0;i<l;i++)
{
if(change(term.word,wordList[i]))
{
if(vis[i]==0)
{
vis[i]=1;
q.push(Node(wordList[i],term.dis+1));
}
}
}
}
return ans;
}
bool change(string a ,string b)
{
int num = 0;
int l = a.length();
for(int i=0;i<l;i++)
{
if(a[i]!=b[i])
num++;
}
if(num==1)
return true;
else
return false;
}
};