Word Ladder II

Intuition

Use simple backtracking (DFS) to explore every possible path from beginWord to endWord.

Approach

1. From current word, try changing every character (a-z).
2. If the new word is in the dictionary, recurse.
3. Keep track of the current path length and only store paths matching the global minimum found so far.

Intuition

A two-step approach:

1. BFS to find the shortest distance from beginWord to all reachable words and map the 'parent-child' relationships.
2. Backtracking (DFS) to traverse the map from endWord back to beginWord (or vice versa) to build only the shortest paths.

Approach

1. Use a Set for wordList for O(1) lookups.
2. BFS Phase: Store the level/distance of each word from beginWord in a HashMap<String, Integer>. This ensures we only move 'forward' in levels during reconstruction.
3. DFS Phase: Start from endWord. For the current word, look at all neighbors (1-char diff). If a neighbor's level is exactly currentLevel - 1, it is part of a shortest path. Recurse until beginWord is reached.
4. Reverse the paths found if you backtracked from end to start.

Dry Run

begin: 'hit', end: 'cog'. BFS: hit(0) -> hot(1) -> {dot, lot}(2) -> {dog, log}(3) -> cog(4). DFS from 'cog': Finds neighbors at level 3 ('dog', 'log'), then their neighbors at level 2, etc.