Word Ladder - II Find All Shortest Transformation Sequences

Graphs

Contents

ProblemExamplesSolutionAlgorithmCodeTimeSpace

Problem Statement❯

Given two words, startWord and targetWord, and a list of unique words wordList, find all the shortest transformation sequences from startWord to targetWord.

  • Each transformed word must exist in wordList.
  • Only one letter can be changed at a time.
  • Each transformation sequence should be as short as possible.

Return all such sequences in any order.

Examples❯

Start Target Word List Result Description
hit cog ["hot","dot","dog","lot","log","cog"] [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]] Two shortest sequences found
hit cog ["hot","dot","dog","lot","log"] [] cog not in wordList, no transformation
a c ["a","b","c"] [["a","c"]] Direct transformation with one letter change
abc def ["dbc","dec","def"] [["abc","dbc","dec","def"]] Chain with exact path

Solution❯

Understanding the Problem

We are given three things: a startWord, a targetWord, and a list of allowed words called wordList.

Our task is to transform startWord into targetWord, but under some important rules:

  • We can only change one letter at a time.
  • Each intermediate word formed during transformation must exist in the wordList.
  • We are not just looking for one sequence, but all shortest sequences that complete the transformation.

This is like finding the shortest paths in a word graph, where each node is a word and edges connect words that differ by only one letter.

Step-by-Step Solution with Example

Step 1: Analyze the Example

Let’s take the example:

startWord = "hit"
targetWord = "cog"
wordList = ["hot", "dot", "dog", "lot", "log", "cog"]

We want to transform "hit" to "cog" using valid intermediate words. Valid paths include: ["hit", "hot", "dot", "dog", "cog"] and ["hit", "hot", "lot", "log", "cog"]. Both have 5 words and are the shortest.

Step 2: Use BFS to Find Levels

We perform Breadth-First Search (BFS) starting from startWord. Why BFS?

  • BFS explores all words level by level — this helps us find the shortest path(s).
  • We build a graph (adjacency list) to remember how each word is connected and from which word it came.
  • We also track the level (or step count) when we reach a word.

Step 3: Stop When Target is Reached

We stop BFS as soon as we reach the targetWord. This ensures we do not explore longer paths than necessary. All words discovered at that level are part of the shortest sequence.

Step 4: Backtrack Using DFS

Once BFS is done, we now backtrack using Depth-First Search (DFS) from the targetWord to startWord, collecting all valid paths:

  • We only move from a word to another word that is one level lower — this keeps the path short.
  • Each path we build represents one valid shortest transformation sequence.

Step 5: Return the Results

All collected paths are stored and returned. Each path shows how we can go from startWord to targetWord using valid transformations.

Edge Cases

  • Target word missing from the word list: If targetWord is not in the wordList, no transformation is possible. We return an empty list.
  • Start word not in list: That’s okay. startWord doesn’t have to be in wordList.
  • No path exists: BFS may complete without ever reaching targetWord. In this case, we also return an empty list.
  • Words of different lengths: All words should be the same length for the one-letter transformation rule to make sense.

Finally

This problem is a combination of graph traversal and path reconstruction. We use BFS to determine the minimum number of steps and build the transformation graph, then DFS to collect all valid shortest paths. The use of two algorithms — BFS followed by DFS — ensures correctness and efficiency.

Understanding the reasoning behind each step — why BFS first, why we backtrack with DFS, and how we prune paths based on levels — helps make this problem clear and approachable even for beginners.

Algorithm Steps❯

  1. Use BFS starting from startWord to generate a graph and record the level (distance) of each word from the start.
  2. While performing BFS, record edges only between valid transformations (words differing by one letter).
  3. If targetWord is not reachable, return an empty list.
  4. Use DFS or backtracking starting from targetWord and move backwards using the levels map to collect all shortest paths.
  5. Return the collected transformation sequences.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
#include <stdio.h>
#include <string.h>

int main() {
    printf("Word Ladder II is too complex for a simple C implementation in one file.\n");
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n * m^2)Best case occurs when the target word is found early during BFS. Here, n is the number of words in the list, and m is the word length. Checking all possible one-letter transformations involves m changes per word and comparing with up to n words.
Average CaseO(n * m^2)On average, we process each word and generate transformations by changing every character (m positions), resulting in n * m comparisons.
Worst CaseO(n * m^2 + k)In the worst case, BFS explores all words, and backtracking (DFS) finds all possible shortest sequences (let's say k sequences). So the total complexity is O(n * m^2 + k).

Space Complexity❯

O(n * m + k)

Explanation: We store the graph (adjacency list), the level map, and the sequences found. Graph and level maps use O(n * m), and storing all k shortest sequences adds O(k).


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...