first bfs to find shortest distance to endWord. then dfs backwards from endWord, only following edges that lead to words at distance d-1, building all paths.
build graph during first bfs: map each word to its neighbors. use distance map to track shortest distance to each word. second pass collects all valid paths.
two-phase approach
- phase 1: bfs to find shortest distance
- phase 2: dfs to collect all shortest paths
- only traverse edges that maintain distance constraint
complexity
O(m * n * 26) for bfs, O(2^d) worst case for dfs where d is depth. space O(n) for graph and paths.