题目：

Given two words (beginWord and endWord), and a dictionary, find the length of shortest transformation sequence from beginWord to endWord, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["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.

代码：

class Solution {
public:
int ladderLength(string beginWord, string endWord, unordered_set& wordDict) {
queue que;
que.push(beginWord); que.push("");
int len = ;
while ( !que.empty() )
{
string curr = que.front();
que.pop();
if (curr!="")
{
for ( size_t i = ; i < curr.size(); ++i )
{
char curr_c = curr[i];
for ( char c='a'; c <= 'z'; ++c )
{
if (c==curr_c) continue;
curr[i] = c;
if (curr==endWord) return len+;
if ( wordDict.find(curr)!=wordDict.end() )
{
que.push(curr);
wordDict.erase(curr);
}
}
curr[i] = curr_c;
}
}
else if ( !que.empty() )
{
len++;
que.push("");
}
}
return ;
}
};

tips：

学习了BFS的思路。

维护一个queue；存放当前word在dict中的所有邻居；末尾加一个空字符""来标示深入一层。

http://www.cnblogs.com/TenosDoIt/p/3443512.html

http://blog.csdn.net/niaokedaoren/article/details/8884938

=============================================

第二次过这道题，上来就打着bfs的幌子写了一个dfs的算法，结果是超时。但也想了一下为什么不能用dfs，dfs会超时的原因是啥：

比如：beginWord = "ab" wordDict{"cb, db"}

如果用dfs的话，就可能会建立出来ab→cb→db 这样即走了冤枉路，也不是最短。

class Solution {
public:
int ladderLength(string beginWord, string endWord, unordered_set& wordDict) {
queue curr;
queue next;
int len = ;
curr.push(beginWord);
while ( !curr.empty() )
{
while ( !curr.empty() )
{
string word = curr.front();
curr.pop();
for ( int i=; i<word.size(); ++i )
{
char ori = word[i];
for ( char c='a'; c<='z'; ++c )
{
if ( c==ori ) continue;
word[i] = c;
if ( word==endWord ) return len+;
if ( wordDict.find(word)!=wordDict.end() )
{
next.push(word);
wordDict.erase(word);
}
}
word[i] = ori;
}
}
if ( next.empty() ) return ;
len++;
swap(next, curr);
}
return ;
}
};