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

We are given a startWord, a targetWord, and a wordList. The goal is to transform the startWord into the targetWord by changing only one character at a time, with the restriction that each transformed word must be a valid word in the given wordList.

This problem can be visualized as a graph where each word is a node, and an edge exists between two words if they differ by exactly one character. Our task is to find the shortest path (in terms of number of transformations) from the startWord to the targetWord. The most suitable algorithm for this task is Breadth-First Search (BFS), which efficiently finds the shortest path in an unweighted graph.

Step-by-Step Solution with Example

Step 1: Check if transformation is possible

If the targetWord is not in the wordList, then there’s no way to reach it via valid transformations. So, we return 0 immediately.

Step 2: Treat words as graph nodes

Each word becomes a node in a graph. Two words are connected by an edge if they differ by exactly one letter. For example, "hot" and "dot" are neighbors, but "hot" and "dog" are not.

Step 3: Use BFS for shortest path

We initialize a queue for BFS with the pair (startWord, level = 1). The level variable tracks how many transformations we've made so far. We also convert the wordList to a set for O(1) lookup and remove the startWord if it's present.

Step 4: Generate possible transformations

For each word we dequeue, we try changing every character to every letter from 'a' to 'z'. For example, from "hot", we generate words like "aot", "bot", ..., "zot", then "hat", "hbt", ..., "hzt", and finally "hoa", "hob", ..., "hoz".

If a transformed word exists in the wordList set, it means we’ve found a valid transformation. We enqueue this new word with level + 1 and remove it from the set to avoid revisiting.

Step 5: Stop when targetWord is found

If during BFS we dequeue a word that matches the targetWord, we return the current level. This ensures the minimum number of steps due to the nature of BFS (shortest path search).

Step 6: Return 0 if targetWord is unreachable

If the BFS completes and we never encounter the targetWord, that means there is no valid transformation path, and we return 0.

Edge Cases

targetWord not in wordList: Return 0 immediately.
startWord is same as targetWord: Usually undefined by the problem, but often treated as requiring at least one transformation, so result should be 0 if no path exists.
wordList is empty: No transformation is possible, return 0.
All words are the same length but differ significantly: The solution should still handle them with correct transformation checks.

Finally

This problem is a great example of using BFS for shortest path discovery in unweighted graphs. By thinking of each word as a node and transformations as edges, we can apply standard graph traversal techniques. Always remember to handle edge cases like missing target words or cycles due to repeated transformations.

With a clear understanding of BFS and word transformation rules, even beginners can confidently approach and solve the Word Ladder problem.

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

Comments

Loading comments...