# Modified BFS

• Using normal bfs, we could easily find the shortest path. However, mark a node instantly after pushing it into the queue could harm us from finding all the shortest paths! Instead, think that bfs partitions all the words into different `'levels'/'layers'`according to their distance from beginWord. The current word `A` (currently polled from the queue) could points to the next word `B` if and only if `B is not visited` or `dist(B,beginWord) = dist(A,beginWord) + 1`.

We could use `Map<String, Integer> vis` memorizing in which `level\layer` the word lies in. If a word is not visited so far, vis[word] = -1.

There could be exponential number of shortest paths, thus time complexity could be that high.

``````public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
/* modified bfs
*  in the normal bfs, we mark the word as visited instantly after pushing it into the queue,
*  which prevent us from finding all the shortest paths. Instead, think that bfs partitions
*  all the words into different 'levels'/'layers' according to their distance from beginWord.
*  The current word A (currently polled from the queue) could points to the next word B if
*  and only if B is not visited or dist(B,beginWord) = dist(A,beginWord) + 1.
*/

// vis[word]: in which level does word lies in, if not visited, vis[word]=-1
Map<String, Integer> vis = new HashMap<>();
// root node
vis.put(beginWord, 0);
for (String word: wordList) vis.put(word, -1);

// parent[word]: the direct parent word pointing to the current word
Map<String, List<String>> parent = new HashMap<>();

q.offer(beginWord);

String cur = "";
int level = 0;
while (!q.isEmpty()) {
cur = q.poll();
level = vis.get(cur);
if (cur.equals(endWord)) break;
for (int i=0; i<cur.length(); i++) {
for (char c='a'; c<='z'; c++) {
String mutated = cur.substring(0,i) + c + cur.substring(i+1,cur.length());
if (!vis.containsKey(mutated)) continue;
int level_of_mutated = vis.get(mutated);
if (level_of_mutated==-1) {
q.offer(mutated);
vis.put(mutated, level+1);
}
else if (level_of_mutated==level+1) {
}
}
}
}

// extract paths
dfs(endWord, beginWord, parent, new LinkedList<String>(), ans);
return ans;
}

public void dfs(String word, String beginWord, Map<String, List<String>>parent, List<String> path, List<List<String>> ans) {
if (word.equals(beginWord)) {
path.remove(0);
return;
}
if (parent.containsKey(word)) {
for (String pa: parent.get(word)) {
dfs(pa, beginWord, parent, path, ans);
}
}
// traceback
path.remove(0);
}
``````

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