I
第一问很简单，本质上就是BFS求无权图上最短路，注意状态转移的方式即可。
II
第二问就很有些难度了，并且也有一类通用的BFS问题解决思路。它要求输出所有的最短路径，这就意味着显然不可能仅仅用BFS来完成任务。因为在状态有限的BFS搜索中，我们绝对不能重复访问一个状态，否则就会导致搜索空间无限增大。
但是如果不能访问重复状态的话，也就意味着我们只能找到互相完全不重叠的最短路，因为一旦两条最短路上存在公共节点，那么这个节点在搜索的过程中只能归属于其中一条路径，而另一条就无法被找到，这是BFS的本质缺陷。
回到题目本身，首先我们注意到，搜索过程中的全部状态，都包含在给出的dict里面，这也就意味着状态空间实际上是很小的。如果我们将整个状态空间看作一个图，那么图中会存在多个最短路径，可以从起始状态抵达终点状态。如果我们在BFS过程中不去试图找出所有答案，而是去试图记录状态之间的相互转移方式——某个状态可以由哪些状态转移得到，这样我们就可以从末状态发起一次DFS，搜索到起始状态，并得出所有答案。DFS的特性保证了我们在搜索过程中能够找到所有的解。
此外，代码实现中包含许多细节，比如需要使用节点来记录状态信息、使用vector数组记录能够转移到当前状态的节点指针、状态转移时需要比较路径长度等等。
代码
struct Node {
string str;
int steps;
vector<Node *> prev;
Node( string &s, int st, Node *p) {
str = s;
steps = st;
prev.push_back(p);
}
};
class Solution {
public:
vector<vector<string> > findLadders(string start, string end, unordered_set<string> &dict) {
vector<string> ans;
vector<vector<string> > res;
unordered_map<string, Node *> visited;
unordered_map<string, Node *> :: iterator iter;
queue<Node *> que;
que.push(new Node(start, 0, NULL));
visited[start] = que.front();
dict.insert(end);
while ( !que.empty() ) {
Node *p = que.front(); que.pop();
string cur = p->str;
int steps = p->steps;
for ( int i = 0; i < cur.size(); i++ ) {
char bak = cur[i];
for ( int j = 0; j < 26; j++ ) {
if ( 'a' + j == bak ) continue;
cur[i] = 'a' + j;
if ( dict.find(cur) != dict.end() ) {
if ( ( iter = visited.find(cur) ) == visited.end() ) {
Node *ptr = new Node(cur, steps + 1, p);
visited[cur] = ptr;
que.push(ptr);
} else if ( iter->second->steps == steps + 1 ) {
iter->second->prev.push_back(p);
}
}
}
cur[i] = bak;
}
}
DFS(visited[end], ans, res);
for ( int i = 0; i < res.size(); i++ ) reverse(res[i].begin(), res[i].end());
return res;
}
void DFS( Node *p, vector<string> & ans, vector<vector<string> > & res ) {
if ( p == NULL ) {
if ( ans.size() > 0 ) res.push_back(ans);
return;
}
for ( int i = 0; i < p->prev.size(); i++ ) {
ans.push_back(p->str);
DFS(p->prev[i], ans, res);
ans.pop_back();
}
}
};