# Solution by bfs and dfs output path.

1. Keep two dictionary to maintain the information of a vertex:

`dist`: the distance to `start`

`prev`: a list of previous vertices on the shortest path.

1. Use dfs to traverse `prev`, output the path from `start` to `end`.

class Solution {
public:
void dfsOutputPath(string end, unordered_map<string, vector<string> >& prev, vector<string> sofar, vector<vector<string> >& res) {
vector<string> newSofar;
newSofar.push_back(end);
newSofar.insert(newSofar.end(), sofar.begin(), sofar.end());

``````     if (prev.count(end) == 0 || prev[end].empty()) {
res.push_back(newSofar);
} else {
vector<string>& prevs = prev[end];
for (int i = 0; i < prevs.size(); ++i) {
dfsOutputPath(prevs[i], prev, newSofar, res);
}
}
}

vector<vector<string> > findLadders(string start, string end, unordered_set<string> &dict) {
if (start == end) return vector<vector<string> >(1, vector<string>(1, start));

vector<vector<string> > res;

// bfs
queue<string> q;
unordered_map<string, int> dist;
unordered_map<string, vector<string> > prev;

dist[start] = 0;
q.push(start);

while (!q.empty()) {
string u = q.front();
q.pop();

if (dist.count(end) > 0 && dist[u] >= dist[end]) break;

// for all (u, v) in E
for (int i = 0; i < u.size(); ++i) {
char c = u[i];
for (int j = 0; j < 26; ++j) {
char swapped = 'a' + j;
if (swapped != c) {
string v(u);
v[i] = swapped;

// in dict
if (dict.count(v) > 0 || v == end) {
// v is not visited
if (dist.count(v) == 0) {
dist[v] = dist[u] + 1;
prev[v] = vector<string>(1, u);
q.push(v);
} else {
// v is on another shortest path
if (dist[v] == dist[u] + 1) {
prev[v].push_back(u);
}
}
}
}
}
}
}

if (dist.count(end) > 0) dfsOutputPath(end, prev, vector<string>(), res);

return res;
}
``````

};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.