Word Ladder - 1 Shortest Transformation Using Graph

Graphs

Contents

ProblemExamplesSolutionAlgorithmCodeTimeSpace

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❯

  1. If targetWord is not in wordList, return 0.
  2. Initialize a queue with a pair: (startWord, 1) where 1 represents the initial level.
  3. Convert wordList into a set for O(1) lookups.
  4. While the queue is not empty:
    1. Dequeue the current word and its level.
    2. If the current word is equal to targetWord, return the level.
    3. Generate all possible one-letter transformations.
    4. If the transformed word is in wordList, enqueue it with level+1 and remove it from the set.
  5. If BFS completes without finding targetWord, return 0.

Code

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

#define MAX 1000

int isOneLetterDiff(const char *a, const char *b) {
    int diff = 0;
    for (int i = 0; a[i]; i++) {
        if (a[i] != b[i]) diff++;
        if (diff > 1) return 0;
    }
    return diff == 1;
}

int wordLadder(char *start, char *end, char **wordList, int size) {
    int visited[MAX] = {0};
    char *queue[MAX];
    int level[MAX];
    int front = 0, rear = 0;

    queue[rear] = start;
    level[rear++] = 1;

    while (front < rear) {
        char *word = queue[front];
        int currLevel = level[front++];

        if (strcmp(word, end) == 0)
            return currLevel;

        for (int i = 0; i < size; i++) {
            if (!visited[i] && isOneLetterDiff(word, wordList[i])) {
                visited[i] = 1;
                queue[rear] = wordList[i];
                level[rear++] = currLevel + 1;
            }
        }
    }

    return 0;
}

int main() {
    char *wordList[] = {"hot", "dot", "dog", "lot", "log", "cog"};
    int size = 6;
    printf("Length of shortest transformation: %d\n", wordLadder("hit", "cog", wordList, size));
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(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 CaseO(m * n)For each word in the wordList, up to m*26 transformations are checked, and each valid transformation is enqueued once.
Worst CaseO(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.


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...