Scale Engineer

Word Ladder II

Hard
#0126Time: O(N * L * b^d)Space: O(N * d * b^d)5 companies
Patterns
Backtracking
Algorithms
Breadth-First Search
Data structures
Hash TableString
Companies
LinkedInTikTokYelpLyft

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

class Solution {    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {        List<List<String>> results = new ArrayList<>();        Set<String> dict = new HashSet<>(wordList);        if (!dict.contains(endWord)) {            return results;        }         Queue<List<String>> queue = new LinkedList<>();        List<String> initialPath = new ArrayList<>();        initialPath.add(beginWord);        queue.offer(initialPath);         Set<String> 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<String> 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<String> 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;    }}

Complexity

Time

O(N * L * b^d)

Space

O(N * d * b^d)

Trade-offs

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.

Solutions

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 (); } } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem