题目：
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
给定两个单词（start 和 and )，以及一个字典，找出从 start 到 end 最短变换序列的长度。
1、一次只能改变一个字母。
2、每个中间词必须在字典中存在。
For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",（从 hit 到 cog
，每个单词变化一个字母）
return its length 5.
Note:
- Return 0 if there is no such transformation sequence.（如果找不到序列，则返回0）。
- All words have the same length.（所有的单词都有相同的长度）。
- All words contain only lowercase alphabetic characters.（所有的单词只包含小写字母）。
思路：
可以使用BFS和DFS，但是DFS会超时，具体分析请看代码。
代码1：
//BFS 1，广度优先搜索，即是（先把start入队列，作为第一层）先找到start能到达的单词（即和当前单词只差一个字母的单词），把它们全部入队列（定义为第二层），
//然后分别对第二层的单词找到它们能到达的单词，再把它们全部入队列（定义为第三层），依次类推，直到找到达到的单词为end。每遍历完一层所求长度+1.
//这里有一个问题就是重复问题，需要定义一个集合用于保存找到的所有单词，用于后续判重
class Solution {
public:
int ladderLength(string start, string end, unordered_set<string> &dict)
{
if(start.size()!=end.size())
return 0;
if(start == end)
return 2;
int min_value = 1;//存储结果长度，初始值有start，所以为1
unordered_set<string> unique;//存储符合条件的单词，主要用于判重（判断后续查找到的单词是否重复）
unique.insert(start);//先把第一层的单词start放入集合
queue<string> que;//队列用于按层次保存单词
que.push(start);//第一层入队列
int q1=1;//当前层次要遍历的单词的个数，初始值为第一层，只有1个单词start
int q2=0;//下一层要遍历的单词的个数
while(q1 > 0)
{
string s = que.front();
que.pop();
--q1;//当前层次单词少一个，q1减一次1
//for循环是在dict中找到当前单词s所能到达的单词（即和s只差一个字母的单词），并入队列
for(int i=0; i<s.size(); i++)
{
string temp = s;
for(char c='a'; c<='z'; c++)
{
//如果当前字符和c相等，则结束下面操作，重新循环
if(temp[i] == c)
continue;
temp[i] = c;//用字符c代替temp的第i个字母，然后再判断替换后的temp是否在dict中
//如果找到的单词和end相等，则结束遍历（因为求最短长度）
if(temp == end)
{
return min_value+1;
}
//替换一个字母后的单词如果在dict中，但是不在unique中，则入队列
if(dict.find(temp)!=dict.end() && unique.find(temp)==dict.end())
{
//把找到的单词temp放入unique中，再入队列，再把下一层要遍历的单词个数+1
unique.insert(temp);
que.push(temp);
++q2;
}
}
}
//如果当前层次的单词遍历完，min_value+1，然后把q2赋给q1，开始遍历下一层
if(q1==0)
{
q1 = q2;
q2 = 0;
++min_value;
}
}
return 0;
}
};
代码2：
//法二：不用上面的方法判重，直接在dict中删除找到的单词
class Solution {
public:
int ladderLength(string start, string end, unordered_set<string> &dict)
{
if(start.size()!=end.size())
return 0;
if(start == end)
return 2;
int min_value = 1;//存储结果长度，初始值有start，所以为1
dict.erase(start);//如果dict中存在start则先删除
queue<string> que;//队列用于按层次保存单词
que.push(start);//第一层入队列
int q1=1;//当前层次要遍历的单词的个数，初始值为第一层，只有1个单词start
int q2=0;//下一层要遍历的单词的个数
while(q1 > 0 && !dict.empty())
{
string s = que.front();
que.pop();
--q1;//当前层次单词少一个，q1减一次1
//for循环是在dict中找到当前单词s所能到达的单词（即和s只差一个字母的单词），并入队列
for(int i=0; i<s.size(); i++)
{
string temp = s;
for(char c='a'; c<='z'; c++)
{
//如果当前字符和c相等，则结束下面操作，重新循环
if(temp[i] == c)
continue;
temp[i] = c;//用字符c代替temp的第i个字母，然后再判断替换后的temp是否在dict中
//如果找到的单词和end相等，则结束遍历（因为求最短长度）
if(temp == end)
{
return min_value+1;
}
//替换一个字母后的单词如果在dict中，但是不在unique中，则入队列
if(dict.find(temp)!=dict.end())
{
dict.erase(temp);//删除找到的temp
que.push(temp);
++q2;
}
}
}
//如果当前层次的单词遍历完，min_value+1，然后把q2赋给q1，开始遍历下一层
if(q1==0)
{
q1 = q2;
q2 = 0;
++min_value;
}
}
return 0;
}
};