# Word Ladder **Difficulty:** HARD [External](https://leetcode.com/problems/word-ladder) Canonical: https://scaleengineer.com/dsa/problems/word-ladder **Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search) **Data structures:** Hash Table, String **Companies:** [LinkedIn](https://scaleengineer.com/companies/linkedin), [Nutanix](https://scaleengineer.com/companies/nutanix), [Samsung](https://scaleengineer.com/companies/samsung), [Tekion](https://scaleengineer.com/companies/tekion), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Visa](https://scaleengineer.com/companies/visa), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yelp](https://scaleengineer.com/companies/yelp), [ZScaler](https://scaleengineer.com/companies/zscaler), [eBay](https://scaleengineer.com/companies/ebay), [Juspay](https://scaleengineer.com/companies/juspay), [Snap](https://scaleengineer.com/companies/snap), [PhonePe](https://scaleengineer.com/companies/phonepe), [Navan](https://scaleengineer.com/companies/navan), [The Trade Desk](https://scaleengineer.com/companies/the-trade-desk), [Box](https://scaleengineer.com/companies/box), [Reddit](https://scaleengineer.com/companies/reddit) --- ## 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 _the **number of words** in the **shortest transformation sequence** from_ `beginWord` _to_ `endWord`_, or_ `0` _if no such sequence exists._ **Example 1:** **Input:** beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] **Output:** 5 **Explanation:** One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long. **Example 2:** **Input:** beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] **Output:** 0 **Explanation:** The endWord "cog" is not in wordList, therefore there is no valid transformation sequence. **Constraints:** * `1 <= beginWord.length <= 10` * `endWord.length == beginWord.length` * `1 <= wordList.length <= 5000` * `wordList[i].length == beginWord.length` * `beginWord`, `endWord`, and `wordList[i]` consist of lowercase English letters. * `beginWord != endWord` * All the words in `wordList` are **unique**. # Approaches ## Brute-Force Breadth-First Search (BFS) This approach models the problem as finding the shortest path in a graph. Each word is a node, and an edge exists between two words if they differ by a single letter. BFS is a standard algorithm for finding the shortest path in an unweighted graph. The brute-force nature comes from how we find adjacent words (neighbors): for each word, we iterate through the entire dictionary to find all words that are one letter away. **Time:** O(N^2 * L) · **Space:** O(N * L) **Pros:** Conceptually simple and relatively easy to implement.; Correctly solves the problem for small inputs. **Cons:** Extremely inefficient for large inputs due to the nested loop structure for finding neighbors (`O(N^2)` work).; Likely to result in a 'Time Limit Exceeded' (TLE) error on most online judges for the given constraints. ### Explanation The fundamental idea is to perform a Breadth-First Search (BFS) starting from `beginWord`. BFS is guaranteed to find the shortest path in terms of the number of edges (or in this case, words) in an unweighted graph. We use a queue to manage the words to visit and a set to keep track of words in the dictionary that we haven't visited yet. The search proceeds in levels, where each level corresponds to an increase in the transformation sequence length. For every word we take from the queue, we search for its neighbors. A neighbor is a word in the dictionary that differs by only one character. The brute-force part is this search: we linearly scan through all available words in the dictionary and compare them character by character with the current word. If we find a neighbor, we add it to the queue and remove it from the dictionary set to avoid revisiting it. The search terminates and returns the current length (`level + 1`) as soon as we find the `endWord`. If the queue empties before the `endWord` is found, no path exists. ```java class Solution { public int ladderLength(String beginWord, String endWord, List wordList) { Set wordSet = new HashSet<>(wordList); if (!wordSet.contains(endWord)) { return 0; } Queue queue = new LinkedList<>(); queue.offer(beginWord); int level = 1; while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { String currentWord = queue.poll(); // Use an iterator to safely remove from wordSet while iterating Iterator iterator = wordSet.iterator(); while (iterator.hasNext()) { String nextWord = iterator.next(); if (isOneLetterApart(currentWord, nextWord)) { if (nextWord.equals(endWord)) { return level + 1; } queue.offer(nextWord); // Remove to prevent cycles and re-processing iterator.remove(); } } } level++; } return 0; } private boolean isOneLetterApart(String s1, String s2) { int diff = 0; for (int i = 0; i < s1.length(); i++) { if (s1.charAt(i) != s2.charAt(i)) { if (++diff > 1) return false; } } return diff == 1; } } ``` ### Algorithm * Convert `wordList` to a `Set` for efficient lookups and removal. Let's call it `wordSet`. * If `endWord` is not in `wordSet`, a transformation is impossible, so return 0. * Initialize a queue for BFS and add `beginWord`. * Initialize a variable `level = 1` to track the length of the transformation sequence. * Start the BFS loop which continues as long as the queue is not empty. * In each iteration of the loop, process all nodes at the current level. The number of nodes is the current size of the queue. * For each `currentWord` dequeued from the queue: * Iterate through all words in the `wordSet`. * For each `nextWord`, check if it's a neighbor of `currentWord` (differs by exactly one letter). * If `nextWord` is a neighbor: * If `nextWord` is the `endWord`, the shortest path is found. Return `level + 1`. * Otherwise, add `nextWord` to the queue for the next level's processing. * Crucially, remove `nextWord` from `wordSet` to mark it as visited, preventing cycles and redundant checks. * After processing all words at the current level, increment `level`. * If the queue becomes empty and `endWord` has not been reached, it means no such path exists. Return 0. ## BFS with Pre-computation of Neighbors This approach improves upon the brute-force BFS by optimizing the neighbor-finding step. Instead of iterating through the entire dictionary for each word, we pre-process the `wordList` to build a more efficient data structure. We create a map where keys are "generic" versions of words (e.g., `h*t` for `hot`) and values are lists of words that match this pattern. This allows us to find all neighbors of a word in `O(L^2)` time instead of `O(N*L)`. **Time:** O(N * L^2) · **Space:** O(N * L^2) **Pros:** Drastically reduces the time complexity compared to the brute-force approach.; Efficient enough to pass the constraints of the problem on most platforms. **Cons:** Requires significant extra space to store the pre-computed map, which can be large if the number of words or their length is high. ### Explanation The main bottleneck of the brute-force approach is finding all words that are one transformation away. We can significantly speed this up with pre-computation. The idea is to group all words in the dictionary that can be intermediate steps for each other. For example, `dot`, `hot`, and `lot` are all neighbors because they can be represented by the generic pattern `*ot`. We can create a hash map where the keys are these generic patterns and the values are lists of words that fit the pattern. First, we iterate through the entire `wordList` and for each word, we generate all its possible generic forms (where one letter is replaced by a wildcard like `*`). We populate our hash map with these mappings. This pre-processing step takes `O(N * L^2)` time. After the map is built, we perform a standard BFS. For any given word, instead of scanning the whole dictionary, we just generate its `L` generic forms, look them up in our map, and instantly get a list of all its neighbors. This makes the neighbor-finding step within the BFS much more efficient. ```java import javafx.util.Pair; // Or define a custom Pair class class Solution { public int ladderLength(String beginWord, String endWord, List wordList) { Set wordSet = new HashSet<>(wordList); if (!wordSet.contains(endWord)) { return 0; } Map> allComboDict = new HashMap<>(); int L = beginWord.length(); wordList.forEach(word -> { for (int i = 0; i < L; i++) { String genericWord = word.substring(0, i) + "*" + word.substring(i + 1, L); List transformations = allComboDict.getOrDefault(genericWord, new ArrayList<>()); transformations.add(word); allComboDict.put(genericWord, transformations); } }); Queue> queue = new LinkedList<>(); queue.offer(new Pair<>(beginWord, 1)); Set visited = new HashSet<>(); visited.add(beginWord); while (!queue.isEmpty()) { Pair node = queue.poll(); String word = node.getKey(); int level = node.getValue(); for (int i = 0; i < L; i++) { String genericWord = word.substring(0, i) + "*" + word.substring(i + 1, L); for (String adjacentWord : allComboDict.getOrDefault(genericWord, new ArrayList<>())) { if (adjacentWord.equals(endWord)) { return level + 1; } if (!visited.contains(adjacentWord)) { visited.add(adjacentWord); queue.offer(new Pair<>(adjacentWord, level + 1)); } } } } return 0; } } ``` ### Algorithm * **Pre-computation Step**: * Create a `HashMap>` named `allComboDict`. * Iterate through each `word` in the `wordList`. * For each `word`, generate all its `L` possible generic forms by replacing one character at a time with a wildcard (e.g., `*`). For `hot`, this would be `*ot`, `h*t`, `ho*`. * For each generic form, add the original `word` to the list of words associated with that generic form in `allComboDict`. * **BFS Step**: * Initialize a queue with a pair containing the `beginWord` and its level, `1`. * Create a `visited` set and add `beginWord` to it. * While the queue is not empty: * Dequeue the current `(word, level)` pair. * Generate all `L` generic forms for the current `word`. * For each generic form, look up the list of matching words (neighbors) in `allComboDict`. * For each `adjacentWord` in this list: * If `adjacentWord` is the `endWord`, return `level + 1`. * If `adjacentWord` has not been visited, add it to the `visited` set and enqueue it with `level + 1`. ## Bidirectional BFS This is the most optimal approach. It builds upon the idea of BFS but runs two simultaneous searches: one forward from `beginWord` and one backward from `endWord`. The algorithm terminates when the two search frontiers meet. This is generally much faster than a standard BFS because it explores a smaller number of nodes. Instead of one search of depth `d`, we have two searches of depth `d/2`, which drastically reduces the search space (`2 * b^(d/2)` vs `b^d`, where `b` is the branching factor). **Time:** O(N * L^2) · **Space:** O(N * L) **Pros:** Significantly faster in practice than unidirectional BFS for most cases, especially for longer paths.; Can be implemented to be very space-efficient (O(N*L)) by generating neighbors on the fly. **Cons:** The implementation is more complex and requires careful management of two queues and two visited sets. ### Explanation Bidirectional search is a powerful optimization for shortest path problems. Instead of exploring outwards from a single point, we start two BFS searches simultaneously, one from the `beginWord` and one from the `endWord`. The search proceeds in levels, but we alternate between expanding the frontier from the beginning and the end. To be most efficient, we always choose to expand the smaller of the two frontiers. This helps to keep the two search areas roughly the same size and ensures we meet in the middle as quickly as possible. A path is found when a word expanded from one search is discovered to have already been visited by the other search. When this happens, we can combine the path from the start to the meeting point and the path from the end to the meeting point to form the full shortest path. The total length is the sum of the levels from both searches. This implementation uses an efficient on-the-fly neighbor generation technique. For a given word, it iterates through each character position, tries all 26 possible lowercase letters, and checks if the resulting new word exists in the dictionary. This avoids the `O(N * L^2)` space complexity of the pre-computation approach, making this method optimal in both time and space. ```java class Solution { public int ladderLength(String beginWord, String endWord, List wordList) { Set wordSet = new HashSet<>(wordList); if (!wordSet.contains(endWord)) { return 0; } Queue queueBegin = new LinkedList<>(); Queue queueEnd = new LinkedList<>(); Map visitedBegin = new HashMap<>(); Map visitedEnd = new HashMap<>(); queueBegin.offer(beginWord); visitedBegin.put(beginWord, 1); queueEnd.offer(endWord); visitedEnd.put(endWord, 1); while (!queueBegin.isEmpty() && !queueEnd.isEmpty()) { // Always expand the smaller queue to keep the search balanced if (queueBegin.size() <= queueEnd.size()) { int result = visitNode(queueBegin, visitedBegin, visitedEnd, wordSet); if (result > -1) return result; } else { int result = visitNode(queueEnd, visitedEnd, visitedBegin, wordSet); if (result > -1) return result; } } return 0; } private int visitNode(Queue queue, Map visited, Map otherVisited, Set wordSet) { String word = queue.poll(); int level = visited.get(word); int L = word.length(); char[] chars = word.toCharArray(); for (int i = 0; i < L; i++) { char originalChar = chars[i]; for (char c = 'a'; c <= 'z'; c++) { chars[i] = c; String adjacentWord = new String(chars); if (otherVisited.containsKey(adjacentWord)) { return level + otherVisited.get(adjacentWord); } if (wordSet.contains(adjacentWord) && !visited.containsKey(adjacentWord)) { visited.put(adjacentWord, level + 1); queue.offer(adjacentWord); } } chars[i] = originalChar; // backtrack } return -1; } } ``` ### Algorithm * Put `wordList` into a `Set` for O(1) lookups. * Initialize two queues: `queueBegin` with `beginWord` and `queueEnd` with `endWord`. * Initialize two `Map`s to track visited nodes and their levels from each direction: `visitedBegin` with `{beginWord: 1}` and `visitedEnd` with `{endWord: 1}`. * While both queues are non-empty: * To keep the search balanced, choose the smaller of the two queues to expand for the current level. * Dequeue a `word` from the chosen queue. Let its level be `level`. * Generate all possible one-letter-different neighbors of `word`. * For each `neighbor`: * Check if this `neighbor` has been visited by the *other* search (i.e., exists in the other `visited` map). If yes, a path has been found. The total length is `level` from the current search plus the level stored in the other map. Return this sum. * If the `neighbor` is a valid word (in the `wordSet`) and has not been visited by the *current* search, add it to the current `visited` map with `level + 1` and enqueue it. * If one of the queues becomes empty, it means the two searches cannot meet, so no path exists. Return 0. # Solutions ### CSharp ```csharp using System.Collections ; using System.Collections.Generic ; using System.Linq ; public class Solution { public int LadderLength ( string beginWord , string endWord , IList < string > wordList ) { var words = Enumerable . Repeat ( beginWord , 1 ). Concat ( wordList ). Select (( word , i ) => new { Word = word , Index = i }). ToList (); var endWordIndex = words . Find ( w => w . Word == endWord )?. Index ; if ( endWordIndex == null ) { return 0 ; } var paths = new List < int >[ words . Count ]; for ( var i = 0 ; i < paths . Length ; ++ i ) { paths [ i ] = new List < int >(); } for ( var i = 0 ; i < beginWord . Length ; ++ i ) { var hashMap = new Hashtable (); foreach ( var item in words ) { var newWord = string . Format ( "{0}_{1}" , item . Word . Substring ( 0 , i ), item . Word . Substring ( i + 1 )); List < int > similars ; if (! hashMap . ContainsKey ( newWord )) { similars = new List < int >(); hashMap . Add ( newWord , similars ); } else { similars = ( List < int >) hashMap [ newWord ]; } foreach ( var similar in similars ) { paths [ similar ]. Add ( item . Index ); paths [ item . Index ]. Add ( similar ); } similars . Add ( item . Index ); } } var left = words . Count - 1 ; var lastRound = new List < int > { 0 }; var visited = new bool [ words . Count ]; visited [ 0 ] = true ; for ( var result = 2 ; left > 0 ; ++ result ) { var thisRound = new List < int >(); foreach ( var index in lastRound ) { foreach ( var next in paths [ index ]) { if (! visited [ next ]) { visited [ next ] = true ; if ( next == endWordIndex ) return result ; thisRound . Add ( next ); } } } if ( thisRound . Count == 0 ) break ; lastRound = thisRound ; } return 0 ; } } ``` ### Java ```java class Solution { private Set < String > words ; public int ladderLength ( String beginWord , String endWord , List < String > wordList ) { words = new HashSet <>( wordList ); if (! words . contains ( endWord )) { return 0 ; } Queue < String > q1 = new ArrayDeque <>(); Queue < String > q2 = new ArrayDeque <>(); Map < String , Integer > m1 = new HashMap <>(); Map < String , Integer > m2 = new HashMap <>(); q1 . offer ( beginWord ); q2 . offer ( endWord ); m1 . put ( beginWord , 0 ); m2 . put ( endWord , 0 ); while (! q1 . isEmpty () && ! q2 . isEmpty ()) { int t = q1 . size () <= q2 . size () ? extend ( m1 , m2 , q1 ) : extend ( m2 , m1 , q2 ); if ( t != - 1 ) { return t + 1 ; } } return 0 ; } private int extend ( Map < String , Integer > m1 , Map < String , Integer > m2 , Queue < String > q ) { for ( int i = q . size (); i > 0 ; -- i ) { String s = q . poll (); int step = m1 . get ( s ); char [] chars = s . 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 (! words . contains ( t ) || m1 . containsKey ( t )) { continue ; } if ( m2 . containsKey ( t )) { return step + 1 + m2 . get ( t ); } q . offer ( t ); m1 . put ( t , step + 1 ); } chars [ j ] = ch ; } } return - 1 ; } } ``` ### Python ```python # native BFS class Solution : def ladderLength ( self , beginWord : str , endWord : str , wordList : List [ str ]) -> int : words = set ( wordList ) q = deque ([ beginWord ]) ans = 1 while q : ans += 1 for _ in range ( len ( q )): s = q . popleft () s = list ( s ) # must convert to list, cannot directly update s[i]='a' for i in range ( len ( s )): ch = s [ i ] for j in range ( 26 ): # will re-generate s itself # but s not in words-set, s removed after added to words-set s [ i ] = chr ( ord ( 'a' ) + j ) t = '' . join ( s ) if t not in words : continue if t == endWord : return ans q . append ( t ) words . remove ( t ) # equivalent to set t as visited s [ i ] = ch # restore return 0 ######### ''' 双向 BFS 是 BFS 常见的一个优化方法，主要实现思路如下： 1. 创建两个队列 q1, q2 分别用于“起点 -> 终点”、“终点 -> 起点”两个方向的搜索； 2. 创建两个哈希表 m1, m2 分别记录访问过的节点以及对应的扩展次数（步数）； 3. 每次搜索时，优先选择元素数量较少的队列进行搜索扩展，如果在扩展过程中，搜索到另一个方向已经访问过的节点，说明找到了最短路径； 4. 只要其中一个队列为空，说明当前方向的搜索已经进行不下去了，说明起点到终点不连通，无需继续搜索。 ''' class Solution : def ladderLength ( self , beginWord : str , endWord : str , wordList : List [ str ]) -> int : def extend ( m1 , m2 , q ): for _ in range ( len ( q )): s = q . popleft () # so, every time, starting from start-word... and later if t in m1 will skip repeated part... step = m1 [ s ] s = list ( s ) # s = "abc", list(s) ==> ['a', 'b', 'c'] for i in range ( len ( s )): ch = s [ i ] for j in range ( 26 ): s [ i ] = chr ( ord ( 'a' ) + j ) t = '' . join ( s ) if t in m1 or t not in words : continue if t in m2 : return step + 1 + m2 [ t ] m1 [ t ] = step + 1 q . append ( t ) s [ i ] = ch return - 1 words = set ( wordList ) if endWord not in words : return 0 q1 , q2 = deque ([ beginWord ]), deque ([ endWord ]) m1 , m2 = { beginWord : 0 }, { endWord : 0 } while q1 and q2 : t = extend ( m1 , m2 , q1 ) if len ( q1 ) <= len ( q2 ) else extend ( m2 , m1 , q2 ) if t != - 1 : return t + 1 return 0 ######### import string from collections import deque class Solution ( object ): def ladderLength ( self , beginWord , endWord , wordList ): """ :type beginWord: str :type endWord: str :type wordList: Set[str] :rtype: 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 : # about yield https://stackoverflow.com/questions/231767/what-does-the-yield-keyword-do-in-python # yield is a keyword that is used like return, except the function will return a generator. yield newWord 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 ): wordList . remove ( nbr ) if nbr == endWord : return length + 1 queue . append ( nbr ) return 0 ########### while q1 and q2 : if len ( q1 ) <= len ( q2 ): # Prioritize the queue with fewer elements for expansion extend ( m1 , m2 , q1 ) else : extend ( m2 , m1 , q2 ) def extend ( m1 , m2 , q ): # New round of expansion for _ in range ( len ( q )): p = q . popleft () step = m1 [ p ] for t in next ( p ): if t in m1 : # Already visited before continue if t in m2 : # The other direction has been searched, indicating that a shortest path has been found return step + 1 + m2 [ t ] q . append ( t ) m1 [ t ] = step + 1 ``` ### CPP ```cpp class Solution { public: int ladderLength(string beginWord, string endWord, vector &wordList) { unordered_set words(wordList.begin(), wordList.end()); if (!words.count(endWord)) return 0; queue q1{{beginWord}}; queue q2{{endWord}}; unordered_map m1; unordered_map m2; m1[beginWord] = 0; m2[endWord] = 0; while (!q1.empty() && !q2.empty()) { int t = q1.size() <= q2.size() ? extend(m1, m2, q1, words) : extend(m2, m1, q2, words); if (t != -1) return t + 1; } return 0; } int extend(unordered_map &m1, unordered_map &m2, queue &q, unordered_set &words) { for (int i = q.size(); i > 0; --i) { string s = q.front(); int step = m1[s]; q.pop(); for (int j = 0; j < s.size(); ++j) { char ch = s[j]; for (char k = 'a'; k <= 'z'; ++k) { s[j] = k; if (!words.count(s) || m1.count(s)) continue; if (m2.count(s)) return step + 1 + m2[s]; m1[s] = step + 1; q.push(s); } s[j] = ch; } } return -1; } }; ```