Word Ladder - II Find All Shortest Transformation Sequences

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

You are given a startWord, a targetWord, and a list of allowed wordList. The goal is to transform startWord to targetWord such that:

Only one letter can be changed at a time.
Each transformed word must exist in the wordList.
You must find all the shortest transformation sequences.

Why Use BFS First?

BFS is ideal here because it explores all nodes level by level. This helps us find the shortest path from startWord to targetWord. As we explore, we also keep track of:

Which word was reached from which other word (edges)
The level (number of steps) required to reach each word

We stop BFS once we reach the targetWord level, ensuring we only explore the shortest paths.

Building the Transformation Graph

We consider two words connected if they differ by only one character. For example, "hit" → "hot" is a valid transformation. We build this graph during BFS traversal.

When No Transformation Exists

If the targetWord is never reached during BFS, it means there’s no possible transformation. In this case, we return an empty list.

Collecting All Shortest Paths

Once the BFS is complete, we use DFS or backtracking to find all shortest transformation sequences. Starting from the targetWord, we backtrack to the startWord using the level information (so we only go from higher to lower levels), ensuring that only the shortest sequences are considered.

Edge Case: Words Not in List

If either startWord or targetWord is not in the wordList, we must handle it properly. Usually, startWord is not required in the list, but targetWord must be in it to allow transformation.

Algorithm Steps❯

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

Code

JavaScript

function wordLadderII(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return [];

  const graph = new Map();
  const level = new Map();
  const res = [];

  const bfs = () => {
    const queue = [beginWord];
    level.set(beginWord, 0);

    while (queue.length) {
      const word = queue.shift();
      const currLevel = level.get(word);
      for (let i = 0; i < word.length; i++) {
        for (let c = 97; c <= 122; c++) {
          const next = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
          if (wordSet.has(next)) {
            if (!level.has(next)) {
              level.set(next, currLevel + 1);
              queue.push(next);
              graph.set(next, [word]);
            } else if (level.get(next) === currLevel + 1) {
              graph.get(next).push(word);
            }
          }
        }
      }
    }
  };

  const dfs = (word, path) => {
    if (word === beginWord) {
      res.push([beginWord, ...path.reverse()]);
      return;
    }
    if (!graph.has(word)) return;
    for (const prev of graph.get(word)) {
      dfs(prev, [...path, word]);
    }
  };

  bfs();
  if (level.has(endWord)) dfs(endWord, []);

  return res;
}

console.log(wordLadderII("hit", "cog", ["hot","dot","dog","lot","log","cog"]));

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(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 Case	O(n * m^2)	On average, we process each word and generate transformations by changing every character (m positions), resulting in n * m comparisons.
Worst Case	O(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).

⬅ Previous TopicWord Ladder - Shortest Transformation using Graph

Next Topic ⮕Number of Distinct Islands using DFS