1.分析题目后，我们发现需要找出一条路径，而这条路径的限制是每次只改变一个字母。因此，这也可以理解为求单元最短路径。
2.我们可以考虑采用DFS或者BFS进行搜索。先看看DFS，DFS每次找出一条到达目标点的路径，但是不确定这条路径是否为最短，所以需要遍历完所有的节点才确定到最终解。
3.而BFS相当于一层一层地往外搜索，所以一旦遇到目标点，那么其记录的路径长度就是最短长度，经过上面的分析，我们可以初步使用BFS进行求解。
4.最初的思路是构建好各个单词的邻居，要构建邻居关系，需要对每个单词遍历一次单词表，时间复杂度为O(n*n)，而BFS的复杂度为O(n)，实际我刚开始也是这么做的，结果超时了。单词量能上到2000以上。
5.为了解决构建邻居超时的问题，我换了一种方法，就是事先不构建邻居，而是在BFS中，通过原来的单词进行字母变换，构建出一个新单词，再去判断这个单词是否在wordList中，假设单词长度为k，每个字母替换26次，BFS的复杂度为O(n)，则总的复杂度为（26*k*n）。这样编写程序能够顺利通过测试，耗时460ms。
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 intermediate word must exist in the word list
For example,
Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Note:
- Return 0 if there is no such transformation sequence.
- All words have the same length.
- All words contain only lowercase alphabetic characters.
AC代码：
[c language=”++”]
class Solution {
public:
int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
map<string, bool> visited;
int wordSize = beginWord.size();
int length = 1;
queue<string> q;
q.push(beginWord);
visited[beginWord] = true;
int count1 = 1;
int count2 = 0;
while (!q.empty())
{
length++;
for (int i = 0; i < count1; ++i)
{
string head = q.front();
q.pop();
string tmp = head;
//替换每个单词的每个字母，看看是否能够在wordList中找到
for (int j = 0; j < wordSize; ++j)
{
tmp = head;
for (int k = 0; k < 26; k++)
{
tmp[j] = ‘a’ + k;
if (wordList.find(tmp) != wordList.end()&&!visited[tmp])
{//找到邻居
visited[tmp] = true;
q.push(tmp);
count2++;
}
if (tmp == endWord)
return length;
}
}
}
count1 = count2;
count2 = 0;
}
return 0;
}
};
[/c]