Skip to main content
Talentd

Word Ladder II - Solution & Explanation

HardHash TableStringBacktrackingBreadth-First Search15 min readAsked at: Amazon, Microsoft, Apple +12
Practice this problem

Problem Statement

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.

Approach Overview

Problem Overview: You are given a beginWord, an endWord, and a dictionary of valid words. Each transformation changes exactly one character and must exist in the dictionary. The task is to return all shortest transformation sequences from the start word to the target word.

Approach 1: Classic Breadth-First Search + Backtracking (O(N * L * 26) time, O(N * L) space)

This approach models the dictionary as an implicit graph where each word connects to words that differ by one character. Use Breadth-First Search starting from beginWord to explore transformations level by level. BFS guarantees the first time you reach endWord is the shortest depth. During traversal, store parent relationships in a map so each word keeps track of the words that led to it at the previous level. Instead of stopping immediately when the target appears, finish the entire BFS layer to capture all shortest paths. After BFS builds the parent graph, run a backtracking DFS from endWord to beginWord to reconstruct every valid shortest sequence. The dictionary lookup is optimized using a hash table. The complexity comes from generating up to 26 * L neighbors for each word.

Approach 2: Bidirectional Breadth-First Search (O(N * L * 26) time, O(N * L) space)

Bidirectional BFS improves practical performance by expanding the search simultaneously from beginWord and endWord. Instead of exploring the entire search space from one side, the algorithm always expands the smaller frontier. When the two frontiers meet, the shortest transformation length is determined. While expanding nodes, build adjacency relationships that record how words connect between levels. After the search completes, run a DFS or backtracking step to enumerate all valid sequences using the recorded transitions. This reduces the number of explored states significantly compared with single-direction BFS, especially when the dictionary is large. The time complexity remains proportional to neighbor generation (N * L * 26), but the explored portion of the graph is often much smaller.

Recommended for interviews: The expected solution combines BFS for shortest path discovery and backtracking to reconstruct all valid sequences. Interviewers want to see that you understand why BFS guarantees minimal transformations and how to store parent relationships for path reconstruction. Bidirectional BFS demonstrates deeper optimization skills and is preferred when the dictionary size is large.

Approach 1: Bidirectional Breadth-First Search

The idea is to optimize the BFS by starting the search from both the beginWord and the endWord simultaneously. This bidirectional approach helps in cutting down the search space significantly as the two searches will meet in the middle.

Initially, we create two sets to track words to visit from the beginning side and the ending side. We also use a visited set to ensure we do not revisit any words.

We alternate the search extensions from one side to another to maintain the balance of the search width for the two meet points.

Due to the bidirectional nature, the time complexity can be greatly reduced compared to a conventional BFS.

This Python code uses a bidirectional approach to construct all possible paths from the beginning to the end word. The set operations ensure efficient word lookups and deletions, while the recursive helper function constructs all paths once the tree is established.

Code

PythonJavaScriptJava

Python

JavaScript

Java

Complexity

Time Complexity: O(N * M * 26) where N is the number of words and M is the word length.
Space Complexity: O(N * M) due to the storage of the graph.

Try this approach in the editor →

Approach 2: Classic Breadth-First Search (BFS)

Using a single queue BFS, we explore transformations level by level. We build a graph where each word is a node, and edges are valid single-letter transformations as they appear in the word list. During BFS, paths are stored and checked for minimum length.

We mark words visited in the current level to avoid loops and unnecessary processing.

Once a complete path is found its length is compared to ensure it’s the smallest, and added to results if valid.

This C code uses a loop-based BFS leveraging basic queue operations to explore each word's path to potential matches. A helper function ensures only one-letter transformations are pursued. The transformation check and BFS implementation are in C style for maximum control over memory and data handling.

Code

CC++C#

C

C++

C#

Complexity

Time Complexity: O(N * M * 26).
Space Complexity: O(N * M).

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaGo

Python

Java

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Bidirectional Breadth-First Search

Time Complexity: O(N * M * 26) where N is the number of words and M is the word length.
Space Complexity: O(N * M) due to the storage of the graph.

Classic Breadth-First Search (BFS)

Time Complexity: O(N * M * 26).
Space Complexity: O(N * M).

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Classic BFS + BacktrackingO(N * L * 26)O(N * L)Standard solution for interviews. Clear logic for finding shortest paths and reconstructing sequences.
Bidirectional BFSO(N * L * 26)O(N * L)Best when the dictionary is large. Expands from both ends to reduce the explored search space.

Video Solution

Word Ladder 2 | Leetcode #126 | BFS + DFS • Techdose • 53,800 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Word Ladder II easy or hard?
Word Ladder II is classified as a Hard problem because it combines multiple concepts: BFS shortest-path search, graph construction from strings, and backtracking to enumerate paths. Handling multiple parents and ensuring only shortest sequences are returned makes the implementation more complex than the basic Word Ladder problem.
How to solve Word Ladder II in O(n)?
A strict O(n) solution is not feasible because each word must generate possible neighbors by modifying characters. The practical optimal approach is BFS with neighbor generation, which runs in about O(N * L * 26). Bidirectional BFS reduces the explored portion of the graph and is the most efficient real-world optimization.
Word Ladder II Python or Java solution?
Python and Java implementations typically use a queue for BFS and a HashMap or dictionary to store parent nodes. After BFS discovers the shortest depth, a recursive backtracking function builds every path from endWord back to beginWord. The same logic works across Python, Java, JavaScript, and C++.
What is the best approach for Word Ladder II?
The most common solution uses Breadth-First Search to discover the shortest transformation depth and then backtracking to reconstruct all paths. BFS guarantees minimal steps because it explores level by level. Parent mappings are stored during traversal so every valid shortest sequence can be rebuilt after the search completes.
Is Word Ladder II asked at Google/Amazon/Meta?
Word Ladder variants are frequently used in interviews at large tech companies including Google, Amazon, and Meta. The problem tests graph modeling, BFS traversal, and path reconstruction techniques. Interviewers often expect a BFS-based shortest path approach combined with backtracking.
What data structure is used in Word Ladder II?
The core data structures include a queue for BFS traversal, a hash set for fast dictionary lookups, and a hash map that stores parent relationships between words. During reconstruction, recursion or a stack is used to backtrack through the parent graph to build each valid sequence.
What is the time complexity of Word Ladder II?
The typical complexity is O(N * L * 26), where N is the number of words in the dictionary and L is the word length. For each word explored by BFS, the algorithm generates up to 26 possible character replacements for each position. Additional DFS backtracking reconstructs paths but does not dominate the overall complexity.

Ready to solve this problem?

Practice Word Ladder II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Groups of Strings

Next

Word Ladder