Word Ladder - 1 Shortest Transformation Using Graph

Problem Statement❯

Given two words startWord and targetWord, and a list of unique words wordList, the Word Ladder problem asks you to find the shortest sequence of transformations that converts startWord into targetWord. Each transformation must change exactly one character and result in a valid word in wordList.

If such a sequence exists, return its length. Otherwise, return 0.

Examples❯

startWord	targetWord	wordList	Output	Description
hit	cog	["hot","dot","dog","lot","log","cog"]	5	hit → hot → dot → dog → cog
hit	cog	["hot","dot","dog","lot","log"]	0	No valid path to targetWord
a	c	["a", "b", "c"]	2	a → c
lost	cost	["lost","cost"]	2	lost → cost
game	thee	["gave","gape","tape","tame","thee"]	0	No valid transformations

Solution❯

Understanding the Problem

The task is to transform a startWord into a targetWord by changing only one character at a time, such that each intermediate word exists in the given wordList. This is a classic example of a shortest path problem in an unweighted graph.

Initial Checks

If the targetWord is not part of the wordList, we can return 0 immediately because it is impossible to reach it by valid transformations.

Using BFS (Breadth-First Search)

BFS is ideal here because we are looking for the shortest path. Each word becomes a node, and there's an edge between two nodes if they differ by exactly one character. We start BFS with the startWord and a level of 1 (indicating the first word in the sequence).

Transformations

For each word we dequeue, we try changing every character to all 26 possible lowercase letters. For example, if the word is "hot", we try words like "aot", "bot", ..., "zot" and then "hat", "hbt", ..., "hzt", and so on. If any of these transformed words is present in the wordList set, it is a valid transformation.

Progressing Through the Graph

Every valid transformation is enqueued with level+1 and removed from the set to prevent revisiting. If at any point we find the targetWord, we return the level. This guarantees the shortest path due to the nature of BFS.

Edge Case: No Path Found

If the BFS completes without reaching the targetWord, it means no transformation path exists, and we return 0.

Algorithm Steps❯

If targetWord is not in wordList, return 0.
Initialize a queue with a pair: (startWord, 1) where 1 represents the initial level.
Convert wordList into a set for O(1) lookups.
While the queue is not empty:

Dequeue the current word and its level.
If the current word is equal to targetWord, return the level.
Generate all possible one-letter transformations.
If the transformed word is in wordList, enqueue it with level+1 and remove it from the set.

If BFS completes without finding targetWord, return 0.

Code

JavaScript

function wordLadder(startWord, targetWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(targetWord)) return 0;

  const queue = [[startWord, 1]];
  while (queue.length > 0) {
    const [word, level] = queue.shift();
    if (word === targetWord) return level;

    for (let i = 0; i < word.length; i++) {
      for (let c = 97; c <= 122; c++) {
        const char = String.fromCharCode(c);
        const newWord = word.slice(0, i) + char + word.slice(i + 1);

        if (wordSet.has(newWord)) {
          queue.push([newWord, level + 1]);
          wordSet.delete(newWord);
        }
      }
    }
  }

  return 0;
}

console.log("Length of shortest transformation:", wordLadder("hit", "cog", ["hot","dot","dog","lot","log","cog"]));

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(m * n)	Where n is the number of words and m is the length of each word. In the best case, the target is found early in the BFS traversal, but we still generate m*26 transformations per word.
Average Case	O(m * n)	For each word in the wordList, up to m*26 transformations are checked, and each valid transformation is enqueued once.
Worst Case	O(m * n)	All words are visited and all possible transformations are generated, each requiring O(m) time. So, total operations are O(m * 26 * n) ≈ O(m * n).

Space Complexity❯

O(n)

Explanation: We store the wordList as a set of size n, and use a queue which can hold up to n elements in the worst case.

⬅ Previous TopicNumber of Enclaves in Grid

Next Topic ⮕Word Ladder II - All Shortest Transformation Sequences