Word Ladder II — BFS Shortest Paths + DFS Reconstruct

Problem

Return ALL shortest transformation sequences from beginWord to endWord.

Approach — BFS Layer + DFS Reconstruct

BFS: record for each word its predecessors in shortest path (parents map)
DFS from endWord backwards to beginWord using parents, collect paths

Time: O(M² * N) | Space: O(M² * N)

Solutions

Python

from collections import deque, defaultdict
class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: list[str]) -> list[list[str]]:
        words=set(wordList)
        if endWord not in words: return []
        parents=defaultdict(set)
        layer={beginWord}
        found=False
        while layer and not found:
            words-=layer; nxt=set()
            for word in layer:
                for i in range(len(word)):
                    for c in 'abcdefghijklmnopqrstuvwxyz':
                        nw=word[:i]+c+word[i+1:]
                        if nw in words:
                            nxt.add(nw); parents[nw].add(word)
                            if nw==endWord: found=True
            layer=nxt
        if not found: return []
        res=[]
        def dfs(word, path):
            if word==beginWord: res.append(list(reversed(path))); return
            for p in parents[word]: path.append(p); dfs(p,path); path.pop()
        dfs(endWord,[endWord]); return res

Complexity

Time: O(M² * N) | Space: O(M² * N)