# Word Ladder II **Difficulty:** HARD [External](https://leetcode.com/problems/word-ladder-ii) Canonical: https://scaleengineer.com/dsa/problems/word-ladder-ii **Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking) **Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search) **Data structures:** Hash Table, String **Companies:** [LinkedIn](https://scaleengineer.com/companies/linkedin), [TikTok](https://scaleengineer.com/companies/tiktok), [Yelp](https://scaleengineer.com/companies/yelp), [Lyft](https://scaleengineer.com/companies/lyft), [Citadel](https://scaleengineer.com/companies/citadel) --- ## Problem A **transformation sequence** from word `beginWord` to word `endWord` using a dictionary `wordList` is a sequence of words `beginWord -> s1 -> s2 -> ... -> sk` such that: * Every adjacent pair of words differs by a single letter. * Every `si` for `1 <= i <= k` is in `wordList`. Note that `beginWord` does not need to be in `wordList`. * `sk == endWord` Given two words, `beginWord` and `endWord`, and a dictionary `wordList`, return _all the **shortest transformation sequences** from_ `beginWord` _to_ `endWord`_, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words_ `[beginWord, s1, s2, ..., sk]`. **Example 1:** **Input:** beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] **Output:** [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]] **Explanation:** There are 2 shortest transformation sequences: "hit" -> "hot" -> "dot" -> "dog" -> "cog" "hit" -> "hot" -> "lot" -> "log" -> "cog" **Example 2:** **Input:** beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] **Output:** [] **Explanation:** The endWord "cog" is not in wordList, therefore there is no valid transformation sequence. **Constraints:** * `1 <= beginWord.length <= 5` * `endWord.length == beginWord.length` * `1 <= wordList.length <= 500` * `wordList[i].length == beginWord.length` * `beginWord`, `endWord`, and `wordList[i]` consist of lowercase English letters. * `beginWord != endWord` * All the words in `wordList` are **unique**. * The **sum** of all shortest transformation sequences does not exceed `105`. # Approaches ## Brute-Force BFS with Path Tracking This approach uses a Breadth-First Search (BFS) to explore the word transformations level by level. To reconstruct the paths, the entire path from the `beginWord` to the current word is stored in the BFS queue. When a path reaches the `endWord`, it's added to a result list. The search continues only up to the level where the first shortest path is found to ensure all collected paths are of minimum length. **Time:** O(N * L * b^d) · **Space:** O(N * d * b^d) **Pros:** Conceptually simple and a direct implementation of the problem statement.; Directly builds the final paths during the search process. **Cons:** Extremely high memory usage because the queue stores complete paths, which can grow exponentially.; High time complexity due to redundant computations. If multiple paths reach the same intermediate word, the search from that word is repeated for each path.; Very likely to cause 'Time Limit Exceeded' or 'Memory Limit Exceeded' errors on non-trivial test cases. ### Explanation This method directly translates the problem into a pathfinding search on a graph. We treat each word as a node and a single-letter difference as an edge. The core of this approach is a BFS, which naturally finds the shortest path in terms of the number of transformations (edges). The main challenge is to find *all* shortest paths. To do this, we store the entire transformation sequence (path) in our BFS queue instead of just the current word. Here's the process: 1. We start with a queue containing a single path: `[beginWord]`. 2. We process the search level by level. For each level, we dequeue all paths of that length. 3. For each path, we look at the last word and find all its valid neighbors (one letter difference, present in the `wordList`). 4. If a neighbor is the `endWord`, we've found a shortest path. We add the full path to our results. We make a note that we've found a solution, which means we don't need to explore any deeper levels. 5. If a neighbor is another valid word, we create a new path by extending the current one and add it to the queue for the next level's processing. 6. A crucial step for correctness and efficiency is to avoid cycles and moving backward. We do this by keeping track of all words visited at the current level. After the level is complete, we remove all these words from our dictionary set. This ensures that in subsequent (longer) paths, we don't revisit these words. While conceptually simple, this approach is highly inefficient as the number of paths can grow exponentially, leading to excessive memory and time consumption. ```java class Solution { public List> findLadders(String beginWord, String endWord, List wordList) { List> results = new ArrayList<>(); Set dict = new HashSet<>(wordList); if (!dict.contains(endWord)) { return results; } Queue> queue = new LinkedList<>(); List initialPath = new ArrayList<>(); initialPath.add(beginWord); queue.offer(initialPath); Set visitedInLevel = new HashSet<>(); visitedInLevel.add(beginWord); boolean found = false; while (!queue.isEmpty()) { int levelSize = queue.size(); // Words visited in the current level are removed from the main dict // after the level is processed to avoid cycles and longer paths. for (String word : visitedInLevel) { dict.remove(word); } visitedInLevel.clear(); if (found) break; // Stop if shortest paths were found in the previous level for (int i = 0; i < levelSize; i++) { List currentPath = queue.poll(); String lastWord = currentPath.get(currentPath.size() - 1); char[] chars = lastWord.toCharArray(); for (int j = 0; j < chars.length; j++) { char originalChar = chars[j]; for (char c = 'a'; c <= 'z'; c++) { chars[j] = c; String newWord = new String(chars); if (dict.contains(newWord)) { List newPath = new ArrayList<>(currentPath); newPath.add(newWord); if (newWord.equals(endWord)) { results.add(newPath); found = true; } else { visitedInLevel.add(newWord); queue.offer(newPath); } } } chars[j] = originalChar; // backtrack } } } return results; } } ``` ### Algorithm - Initialize a queue to store paths (lists of words). Add the initial path `[beginWord]`. - Convert `wordList` to a `Set` for efficient O(1) lookups. - Perform a level-by-level Breadth-First Search (BFS). - In each level, process all paths currently in the queue. - For each path, take the last word and generate all its one-letter-different neighbors. - If a neighbor is the `endWord`, a shortest path is found. Add this complete path to the results list and set a flag `found` to true. - If a neighbor is a valid word in the dictionary and hasn't been visited in the current level, create a new path by appending the neighbor and add it to the queue. Keep track of these newly visited words in a `visitedInLevel` set. - After a level is fully processed, if `found` is true, terminate the search. - Otherwise, remove all words in `visitedInLevel` from the main dictionary set to prevent cycles and longer paths. Continue to the next level. ## Two-Pass: BFS to Build Graph + DFS to Find Paths This is a more optimized, two-pass approach. The first pass uses Breadth-First Search (BFS) to find the shortest distance from `beginWord` to all other words. During this BFS, it constructs a directed graph that only contains the edges that are part of any shortest path. The second pass uses Depth-First Search (DFS) on this graph, starting from `beginWord`, to reconstruct all the shortest paths to `endWord`. **Time:** O(N * L^2) · **Space:** O(N * L) **Pros:** Much more efficient in time and space compared to the naive BFS.; Avoids storing entire paths in the BFS queue, preventing exponential memory growth.; Systematically finds the shortest path graph structure before reconstructing the paths. **Cons:** More complex to implement due to the two-pass nature (BFS then DFS).; The initial BFS might still explore a large portion of the graph if the `endWord` is far away or the graph is dense. ### Explanation This approach decouples the problem into two distinct phases to overcome the inefficiencies of the naive method. **Phase 1: BFS for Distances and Graph Building** Instead of storing full paths, the BFS pass focuses on finding the shortest distance from `beginWord` to every other reachable word. It simultaneously builds a directed acyclic graph (DAG) representing all shortest path connections. - We use a `distances` map (`String -> Integer`) to keep track of the shortest level/distance for each word from `beginWord`. This also serves to mark words as visited. - We use an adjacency list (`Map> adj`) to store the DAG. An edge `u -> v` is added to this graph only if moving from `u` to `v` follows a shortest path (i.e., `distance(v) = distance(u) + 1`). - The BFS proceeds level by level. When considering a word `u`, we generate its neighbors `v`. If `v` is on the next level, we add the edge `u -> v` to our `adj` map. This way, we capture all branches that contribute to a shortest path. **Phase 2: DFS for Path Reconstruction** Once the BFS completes, we have a compact representation (`adj`) of all shortest paths. Now, we can efficiently find all the actual path sequences. - We perform a standard Depth-First Search (DFS) starting from `beginWord` and traversing only the edges present in our `adj` graph. - We maintain a `currentPath` list. Whenever the DFS reaches the `endWord`, we have found a complete shortest path, which we add to our final results. - Backtracking is used to explore all possible routes through the `adj` graph. This method is significantly more efficient because it avoids storing redundant path information during the initial exploration phase. ```java class Solution { private Map> adj = new HashMap<>(); private List> results = new ArrayList<>(); private List path = new ArrayList<>(); public List> findLadders(String beginWord, String endWord, List wordList) { Set dict = new HashSet<>(wordList); if (!dict.contains(endWord)) { return results; } // Step 1: BFS to find shortest path lengths and build adj list bfs(beginWord, endWord, dict); // Step 2: DFS to find all paths using the adj list path.add(beginWord); dfs(beginWord, endWord); return results; } private void bfs(String beginWord, String endWord, Set dict) { Map distances = new HashMap<>(); Queue queue = new LinkedList<>(); queue.offer(beginWord); distances.put(beginWord, 0); boolean found = false; while (!queue.isEmpty()) { int size = queue.size(); if (found) break; for (int i = 0; i < size; i++) { String currentWord = queue.poll(); int currentDist = distances.get(currentWord); char[] chars = currentWord.toCharArray(); for (int j = 0; j < chars.length; j++) { char originalChar = chars[j]; for (char c = 'a'; c <= 'z'; c++) { chars[j] = c; String newWord = new String(chars); if (dict.contains(newWord)) { if (!distances.containsKey(newWord)) { // First time visiting this word distances.put(newWord, currentDist + 1); if (newWord.equals(endWord)) found = true; queue.offer(newWord); adj.computeIfAbsent(currentWord, k -> new ArrayList<>()).add(newWord); } else if (distances.get(newWord) == currentDist + 1) { // Found another path of the same shortest length adj.computeIfAbsent(currentWord, k -> new ArrayList<>()).add(newWord); } } } chars[j] = originalChar; // backtrack } } } } private void dfs(String currentWord, String endWord) { if (currentWord.equals(endWord)) { results.add(new ArrayList<>(path)); return; } if (adj.containsKey(currentWord)) { for (String nextWord : adj.get(currentWord)) { path.add(nextWord); dfs(nextWord, endWord); path.remove(path.size() - 1); // backtrack } } } } ``` ### Algorithm **Pass 1: BFS to Build Shortest Path Graph** - Initialize a `distances` map to store the shortest distance from `beginWord` to each word. - Initialize an adjacency list map `adj` to store the directed graph of shortest paths. - Use a queue and perform a level-by-level BFS starting from `beginWord`. - For each word `u` at the current level, find all its neighbors `v`. - If `v` has not been visited (`!distances.containsKey(v)`), update its distance, add an edge `u -> v` to `adj`, and enqueue `v`. - If `v` has been visited but is on the next level (`distances.get(v) == distances.get(u) + 1`), it means we found another shortest path to `v`. Add the edge `u -> v` to `adj`. **Pass 2: DFS to Reconstruct Paths** - Initialize an empty list for results and a list for the current path. - Start a recursive DFS from `beginWord`. - The DFS function explores the `adj` graph. When it reaches `endWord`, the current path is a valid shortest path and is added to the results. - Use backtracking to explore all possible paths from each node in the `adj` graph. ## Optimal: Bidirectional BFS + DFS This approach optimizes the graph-building phase of the previous method by using a bidirectional BFS. Instead of searching only from `beginWord` outwards, we simultaneously search from `endWord` backwards. The search stops when the two search frontiers meet. This significantly prunes the search space, as the number of nodes explored is proportional to `b^(d/2) + b^(d/2)` instead of `b^d` (where `b` is the branching factor and `d` is the path length). After the shortest path graph is built, a DFS is used, as before, to reconstruct all the paths. **Time:** O(N * L^2) · **Space:** O(N * L) **Pros:** The most efficient approach in terms of time complexity for finding the shortest path structure.; Significantly reduces the search space compared to a unidirectional BFS, making it much faster in practice. **Cons:** The implementation is the most complex of the three approaches.; Care must be taken to correctly handle the meeting of the two searches and build the directed graph for the DFS pass, especially with respect to edge direction. ### Explanation This is the most optimal solution, which improves upon the BFS+DFS approach by making the initial graph-building phase faster. **Phase 1: Bidirectional BFS** The key idea is that searching from both the start and end points simultaneously and meeting in the middle is much faster than searching the entire distance from one end. The search space of a BFS grows exponentially with its radius. By using two searches of radius `d/2`, the total explored space `2 * b^(d/2)` is much smaller than `b^d` for a single search. - We maintain two search frontiers, `beginSet` and `endSet`. - In each step of the loop, we choose to expand the smaller of the two sets. This ensures the two search radii remain roughly equal, maximizing the efficiency gain. - As we expand, we build the same `adj` graph as in the previous approach, containing only edges on shortest paths. - The search terminates once a word from one set is found to be a neighbor of a word in the other set. We must complete the current level to find all such meeting points that correspond to the shortest path length. **Phase 2: DFS for Path Reconstruction** This phase remains unchanged. The bidirectional BFS produces the exact same shortest-path DAG (`adj` map) as the unidirectional BFS, just more quickly. We then apply the same DFS traversal on this graph starting from `beginWord` to enumerate all the paths. ```java class Solution { private Map> adj = new HashMap<>(); private List> results = new ArrayList<>(); private List path = new ArrayList<>(); public List> findLadders(String beginWord, String endWord, List wordList) { Set dict = new HashSet<>(wordList); if (!dict.contains(endWord)) { return results; } // Step 1: Bidirectional BFS to build the graph biBfs(beginWord, endWord, dict); // Step 2: DFS to reconstruct paths path.add(beginWord); dfs(beginWord, endWord); return results; } private void biBfs(String beginWord, String endWord, Set dict) { Set beginSet = new HashSet<>(); beginSet.add(beginWord); Set endSet = new HashSet<>(); endSet.add(endWord); boolean found = false; boolean reversed = false; // false: forward (begin->end), true: backward (end->begin) while (!beginSet.isEmpty() && !found) { // Words in the current frontier are effectively visited at this level dict.removeAll(beginSet); Set nextLevelSet = new HashSet<>(); for (String word : beginSet) { char[] chars = word.toCharArray(); for (int i = 0; i < chars.length; i++) { char originalChar = chars[i]; for (char c = 'a'; c <= 'z'; c++) { chars[i] = c; String newWord = new String(chars); String parent = reversed ? newWord : word; String child = reversed ? word : newWord; if (endSet.contains(newWord)) { found = true; adj.computeIfAbsent(parent, k -> new ArrayList<>()).add(child); } else if (dict.contains(newWord)) { nextLevelSet.add(newWord); adj.computeIfAbsent(parent, k -> new ArrayList<>()).add(child); } } chars[i] = originalChar; } } beginSet = nextLevelSet; if (beginSet.size() > endSet.size()) { Set temp = beginSet; beginSet = endSet; endSet = temp; reversed = !reversed; } } } private void dfs(String currentWord, String endWord) { if (currentWord.equals(endWord)) { results.add(new ArrayList<>(path)); return; } if (adj.containsKey(currentWord)) { for (String nextWord : adj.get(currentWord)) { path.add(nextWord); dfs(nextWord, endWord); path.remove(path.size() - 1); } } } } ``` ### Algorithm **Pass 1: Bidirectional BFS to Build Graph** - Initialize two sets, `beginSet` and `endSet`, for the two search frontiers, starting with `beginWord` and `endWord`. - Initialize an adjacency list map `adj` to store the directed graph. - In a loop, always expand the smaller of the two sets to keep the search balanced. - When expanding a word `u` from `beginSet`, generate its neighbors `v`. - If a neighbor `v` is found in the `endSet`, a shortest path has been found. Add the corresponding edge to `adj` and set a `found` flag. - If a neighbor `v` is a new word (not yet visited by either search), add it to a `nextLevelSet` and add the edge to `adj`. - Be careful to maintain the correct direction of edges in `adj` (e.g., always from the `beginWord` side towards the `endWord` side). - Once a path is found, finish the current level to find all meeting points at the same shortest distance, then stop the BFS. **Pass 2: DFS to Reconstruct Paths** - This pass is identical to the one in the previous approach. Use the `adj` graph built by the bidirectional BFS and run a DFS from `beginWord` to find and store all paths. # Solutions ### Java ```java import java.util.ArrayList ; import java.util.Arrays ; import java.util.HashMap ; import java.util.HashSet ; import java.util.LinkedList ; import java.util.List ; import java.util.Queue ; import java.util.Set ; public class Word_Ladder_II { // iteration bfs // https://leetcode.com/problems/word-ladder-ii/solution/ public class Solution { List < List < String >> list = new ArrayList < List < String >>(); public List < List < String >> findLadders ( String start , String end , Set < String > dict ) { if ( start == null || end == null || dict == null ) return list ; dict . add ( end ); // !!! Queue < String > q = new LinkedList < String >(); int level = 1 ; int currentLevelCount = 1 ; int newLevelCount = 0 ; boolean found = false ; int foundLevel = - 1 ; // from end word, to all paths HashMap < String , ArrayList < ArrayList < String >>> hm = new HashMap < String , ArrayList < ArrayList < String >>>(); q . offer ( start ); ArrayList < String > singlePath = new ArrayList < String >(); ArrayList < ArrayList < String >> allPaths = new ArrayList < ArrayList < String >>(); singlePath . add ( start ); allPaths . add ( singlePath ); hm . put ( start , allPaths ); while (! q . isEmpty ()) { String current = q . poll (); currentLevelCount --; // 这里用了新旧count来标记每个level，没有用null for ( int i = 0 ; i < current . length (); i ++) { char [] array = current . toCharArray (); for ( char c = 'a' ; c <= 'z' ; c ++) { array [ i ] = c ; String each = new String ( array ); if ( each . equals ( end )) { found = true ; foundLevel = level ; } if ( dict . contains ( each )) { // q.offer(each); newLevelCount ++; ArrayList < ArrayList < String >> prevAllPaths = hm . get ( current ); if ( hm . containsKey ( each )) allPaths = hm . get ( each ); else { /* @note@note: enqueue is here. if no path ending at this one, then has to explore in future if there is path ending at this one, meaning it's been explored already. no need to enqueue */ q . offer ( each ); allPaths = new ArrayList < ArrayList < String >>(); hm . put ( each , allPaths ); } // @note@note: this if is the key !!! no path for new word, or new word path is one more than previous path // using this if, the"if visited" check can be removed // if (allPaths.size() == 0 || prevAllPaths.size() + 1 == allPaths.size()) { if ( allPaths . size () == 0 || prevAllPaths . get ( 0 ). size () + 1 == allPaths . get ( 0 ). size ()) { for ( ArrayList < String > eachPath : prevAllPaths ) { ArrayList < String > newone = new ArrayList < String >( eachPath ); newone . add ( each ); allPaths . add ( newone ); } } } } } // @note@note: also the key, to make sure only find shortest if ( found && foundLevel != level ) { break ; } // @note: must be after trying the last word of currentLevel, then update if ( currentLevelCount == 0 ) { currentLevelCount = newLevelCount ; newLevelCount = 0 ; level ++; } } if (! found ) { return list ; } for ( ArrayList < String > each : hm . get ( end )) { list . add ( each ); } return list ; } } public class Solution_recursion { private List < String > findPath ( String fromWord , String toWord , Set < String > seenWords ) { if ( fromWord . equals ( toWord )) { ArrayList < String > result = new ArrayList <>(); result . add ( toWord ); return result ; } // Find all words that you can go to from fromWord List < String > nextWords = getNextWords ( fromWord , seenWords ); for ( String word : nextWords ) { Set < String > newSeenWords = new HashSet < String >( seenWords ); newSeenWords . add ( word ); List < String > subPath = findPath ( word , toWord , newSeenWords ); if ( subPath != null ) { subPath . add ( fromWord ); return subPath ; } } // There wasn't a path return null ; } private final List < String > WORDS = Arrays . asList ( "head" , "heal" , "teal" , "tell" , "tall" , "tail" ); private final List < Character > ALPHA = Arrays . asList ( 'a' , 'b' , 'c' , 'd' , 'e' , 'f' , 'g' , 'h' , 'i' , 'j' , 'k' , 'l' , 'm' , 'n' , 'o' , 'p' , 'q' , 'r' , 's' , 't' , 'u' , 'v' , 'w' , 'x' , 'y' , 'z' ); private final HashSet < String > DICTIONARY = new HashSet < String >( WORDS ); private List < String > getNextWords ( String fromWord , Set < String > seenWords ) { List < String > outList = new ArrayList < String >(); StringBuilder builder ; for ( int i = 0 ; i < fromWord . length (); i ++) { builder = new StringBuilder ( fromWord ); for ( Character j : ALPHA ) { if ( j == fromWord . charAt ( i )) { continue ; } builder . setCharAt ( i , j ); String potentialWord = builder . toString (); if ( DICTIONARY . contains ( potentialWord ) && ! seenWords . contains ( potentialWord )) { outList . add ( potentialWord ); } } } return outList ; } } } ////// class Solution { private List < List < String >> ans ; private Map < String , Set < String >> prev ; public List < List < String >> findLadders ( String beginWord , String endWord , List < String > wordList ) { ans = new ArrayList <>(); Set < String > words = new HashSet <>( wordList ); if (! words . contains ( endWord )) { return ans ; } words . remove ( beginWord ); Map < String , Integer > dist = new HashMap <>(); dist . put ( beginWord , 0 ); prev = new HashMap <>(); Queue < String > q = new ArrayDeque <>(); q . offer ( beginWord ); boolean found = false ; int step = 0 ; while (! q . isEmpty () && ! found ) { ++ step ; for ( int i = q . size (); i > 0 ; -- i ) { String p = q . poll (); char [] chars = p . toCharArray (); for ( int j = 0 ; j < chars . length ; ++ j ) { char ch = chars [ j ]; for ( char k = 'a' ; k <= 'z' ; ++ k ) { chars [ j ] = k ; String t = new String ( chars ); if ( dist . getOrDefault ( t , 0 ) == step ) { prev . get ( t ). add ( p ); } if (! words . contains ( t )) { continue ; } prev . computeIfAbsent ( t , key -> new HashSet <>()). add ( p ); words . remove ( t ); q . offer ( t ); dist . put ( t , step ); if ( endWord . equals ( t )) { found = true ; } } chars [ j ] = ch ; } } } if ( found ) { Deque < String > path = new ArrayDeque <>(); path . add ( endWord ); dfs ( path , beginWord , endWord ); } return ans ; } private void dfs ( Deque < String > path , String beginWord , String cur ) { if ( cur . equals ( beginWord )) { ans . add ( new ArrayList <>( path )); return ; } for ( String precursor : prev . get ( cur )) { path . addFirst ( precursor ); dfs ( path , beginWord , precursor ); path . removeFirst (); } } } ``` ### Python ```python ''' remove() same as discard() >>> a = set([11,22,33]) >>> a.remove(22) >>> a {33, 11} >>> a = set([11,22,33]) >>> a.discard(22) >>> a {33, 11} >>> a=set([1,2,3]) >>> a.discard(555) >>> a.remove(555) Traceback (most recent call last): File "", line 1, in KeyError: 555 ''' class Solution : def findLadders ( self , beginWord : str , endWord : str , wordList : List [ str ] ) -> List [ List [ str ]]: # endWord to beginWord # better than begin to end, too many paths not in final result def dfs ( path , cur ): if cur == beginWord : ans . append ( path [:: - 1 ]) return for precursor in prev [ cur ]: path . append ( precursor ) dfs ( path , precursor ) path . pop () ans = [] words = set ( wordList ) if endWord not in words : return ans # no exception if beginWord not in set words . discard ( beginWord ) dist = { beginWord : 0 } prev = defaultdict ( set ) q = deque ([ beginWord ]) found = False step = 0 while q and not found : step += 1 for _ in range ( len ( q ), 0 , - 1 ): p = q . popleft () s = list ( p ) for i in range ( len ( s )): ch = s [ i ] for j in range ( 26 ): s [ i ] = chr ( ord ( 'a' ) + j ) t = '' . join ( s ) if dist . get ( t , 0 ) == step : prev [ t ]. add ( p ) # repeated 3 lines below if t not in words : # if above '== step' met, then t must be removed from words[] from previous iterations continue prev [ t ]. add ( p ) # repeated 3 lines above words . discard ( t ) q . append ( t ) dist [ t ] = step if endWord == t : found = True s [ i ] = ch if found : path = [ endWord ] dfs ( path , endWord ) return ans ############ from collections import deque class Solution ( object ): def findLadders ( self , beginWord , endWord , wordlist ): """ :type beginWord: str :type endWord: str :type wordlist: Set[str] :rtype: List[List[int]] """ def getNbrs ( src , dest , wordList ): res = [] for c in string . ascii_lowercase : for i in range ( 0 , len ( src )): newWord = src [: i ] + c + src [ i + 1 :] if newWord == src : continue if newWord in wordList or newWord == dest : yield newWord def bfs ( beginWord , endWord , wordList ): distance = { beginWord : 0 } queue = deque ([ beginWord ]) length = 0 while queue : length += 1 for k in range ( 0 , len ( queue )): top = queue . popleft () for nbr in getNbrs ( top , endWord , wordList ): if nbr not in distance : distance [ nbr ] = distance [ top ] + 1 queue . append ( nbr ) return distance def dfs ( beginWord , endWord , wordList , path , res , distance ): if beginWord == endWord : res . append ( path + []) return for nbr in getNbrs ( beginWord , endWord , wordList ): if distance . get ( nbr , - 2 ) + 1 == distance [ beginWord ]: path . append ( nbr ) dfs ( nbr , endWord , wordList , path , res , distance ) path . pop () res = [] distance = bfs ( endWord , beginWord , wordlist ) dfs ( beginWord , endWord , wordlist , [ beginWord ], res , distance ) return res ```