Word Ladder - Shortest Transformation using Graph

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.

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.

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.

#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;
}

#include <iostream>
#include <queue>
#include <unordered_set>
using namespace std;

bool oneLetterDiff(const string &a, const string &b) {
    int diff = 0;
    for (int i = 0; i < a.size(); ++i)
        if (a[i] != b[i] && ++diff > 1) return false;
    return diff == 1;
}

int wordLadder(string start, string end, vector<string>& wordList) {
    unordered_set<string> wordSet(wordList.begin(), wordList.end());
    if (!wordSet.count(end)) return 0;

    queue<pair<string, int>> q;
    q.push({start, 1});

    while (!q.empty()) {
        auto [word, level] = q.front(); q.pop();
        if (word == end) return level;

        for (int i = 0; i < word.size(); ++i) {
            string temp = word;
            for (char c = 'a'; c <= 'z'; ++c) {
                temp[i] = c;
                if (wordSet.count(temp)) {
                    q.push({temp, level + 1});
                    wordSet.erase(temp);
                }
            }
        }
    }

    return 0;
}

int main() {
    vector<string> wordList = {"hot", "dot", "dog", "lot", "log", "cog"};
    cout << "Length of shortest transformation: " << wordLadder("hit", "cog", wordList) << endl;
    return 0;
}

from collections import deque

def word_ladder(start_word, target_word, word_list):
    word_set = set(word_list)
    if target_word not in word_set:
        return 0

    queue = deque([(start_word, 1)])
    while queue:
        word, level = queue.popleft()
        if word == target_word:
            return level

        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                new_word = word[:i] + c + word[i+1:]
                if new_word in word_set:
                    queue.append((new_word, level + 1))
                    word_set.remove(new_word)

    return 0

print("Length of shortest transformation:", word_ladder("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]))

import java.util.*;

public class WordLadderSolver {
    public static int wordLadder(String start, String target, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(target)) return 0;

        Queue<String> queue = new LinkedList<>();
        queue.offer(start);
        int level = 1;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String word = queue.poll();
                if (word.equals(target)) return level;
                for (int j = 0; j < word.length(); j++) {
                    char[] chars = word.toCharArray();
                    for (char c = 'a'; c <= 'z'; c++) {
                        chars[j] = c;
                        String newWord = new String(chars);
                        if (wordSet.contains(newWord)) {
                            queue.offer(newWord);
                            wordSet.remove(newWord);
                        }
                    }
                }
            }
            level++;
        }
        return 0;
    }

    public static void main(String[] args) {
        List<String> words = Arrays.asList("hot", "dot", "dog", "lot", "log", "cog");
        System.out.println("Length of shortest transformation: " + wordLadder("hit", "cog", words));
    }
}

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"]));

package main

import (
    "fmt"
)

func wordLadder(start, target string, wordList []string) int {
    wordSet := make(map[string]bool)
    for _, word := range wordList {
        wordSet[word] = true
    }
    if !wordSet[target] {
        return 0
    }

    queue := []struct {
        word  string
        level int
    }{{start, 1}}

    for len(queue) > 0 {
        current := queue[0]
        queue = queue[1:]

        if current.word == target {
            return current.level
        }

        for i := 0; i < len(current.word); i++ {
            for c := 'a'; c <= 'z'; c++ {
                next := []rune(current.word)
                next[i] = c
                newWord := string(next)
                if wordSet[newWord] {
                    queue = append(queue, struct {
                        word  string
                        level int
                    }{newWord, current.level + 1})
                    delete(wordSet, newWord)
                }
            }
        }
    }

    return 0
}

func main() {
    wordList := []string{"hot", "dot", "dog", "lot", "log", "cog"}
    fmt.Println("Length of shortest transformation:", wordLadder("hit", "cog", wordList))
}

use std::collections::{HashSet, VecDeque};

fn word_ladder(start: &str, target: &str, word_list: Vec<String>) -> i32 {
    let mut word_set: HashSet<String> = word_list.into_iter().collect();
    if !word_set.contains(target) {
        return 0;
    }
    let mut queue = VecDeque::new();
    queue.push_back((start.to_string(), 1));

    while let Some((word, level)) = queue.pop_front() {
        if word == target {
            return level;
        }

        let word_chars: Vec<char> = word.chars().collect();
        for i in 0..word_chars.len() {
            for c in b'a'..=b'z' {
                let mut next = word_chars.clone();
                next[i] = c as char;
                let new_word: String = next.iter().collect();
                if word_set.remove(&new_word) {
                    queue.push_back((new_word, level + 1));
                }
            }
        }
    }

    0
}

fn main() {
    let words = vec!["hot", "dot", "dog", "lot", "log", "cog"]
        .into_iter().map(String::from).collect();
    println!("Length of shortest transformation: {}", word_ladder("hit", "cog", words));
}

fun wordLadder(start: String, target: String, wordList: List<String>): Int {
    val wordSet = wordList.toMutableSet()
    if (target !in wordSet) return 0

    val queue: ArrayDeque<Pair<String, Int>> = ArrayDeque()
    queue.add(start to 1)

    while (queue.isNotEmpty()) {
        val (word, level) = queue.removeFirst()
        if (word == target) return level

        for (i in word.indices) {
            for (c in 'a'..'z') {
                val newWord = word.substring(0, i) + c + word.substring(i + 1)
                if (newWord in wordSet) {
                    queue.add(newWord to (level + 1))
                    wordSet.remove(newWord)
                }
            }
        }
    }
    return 0
}

fun main() {
    val words = listOf("hot", "dot", "dog", "lot", "log", "cog")
    println("Length of shortest transformation: ${wordLadder("hit", "cog", words)}")
}

import Foundation

func wordLadder(_ start: String, _ target: String, _ wordList: [String]) -> Int {
    var wordSet = Set(wordList)
    if !wordSet.contains(target) { return 0 }

    var queue: [(String, Int)] = [(start, 1)]

    while !queue.isEmpty {
        let (word, level) = queue.removeFirst()
        if word == target { return level }

        for i in word.indices {
            for c in "abcdefghijklmnopqrstuvwxyz" {
                var chars = Array(word)
                chars[word.distance(from: word.startIndex, to: i)] = c
                let newWord = String(chars)
                if wordSet.contains(newWord) {
                    queue.append((newWord, level + 1))
                    wordSet.remove(newWord)
                }
            }
        }
    }

    return 0
}

let words = ["hot", "dot", "dog", "lot", "log", "cog"]
print("Length of shortest transformation:", wordLadder("hit", "cog", words))

function wordLadder(startWord: string, targetWord: string, wordList: string[]): number {
  const wordSet: Set<string> = new Set(wordList);
  if (!wordSet.has(targetWord)) return 0;

  const queue: [string, number][] = [[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

Space complexity

O(n)

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.