127. Word Ladder - Solution & Explanation

The problem

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s₁ -> s₂ -> ... -> s_k such that:

Every adjacent pair of words differs by a single letter.
Every s_i for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
s_k == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

Example 2:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.

Constraints:

1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord, endWord, and wordList[i] consist of lowercase English letters.
beginWord != endWord
All the words in wordList are unique.

Approach overview

Problem Overview: Given a beginWord, endWord, and a dictionary of valid words, compute the length of the shortest transformation sequence where only one character can change at a time and every intermediate word must exist in the dictionary.

Approach 1: Graph Construction + Breadth‑First Search (O(N^2 * L) time, O(N^2) space)

Treat every word as a node in a graph. Two nodes connect if the words differ by exactly one character. Building this graph requires comparing every pair of words and checking if they differ by one position, which costs O(N^2 * L) where N is the number of words and L is the word length. After constructing the adjacency list, run Breadth‑First Search from beginWord to find the shortest path to endWord. BFS guarantees the minimum number of transformations because it explores level by level. This approach is conceptually simple but wastes time building a dense graph that may never be fully explored.

Approach 2: BFS with Word Transformations (O(N * L * 26) time, O(N) space)

The optimized solution avoids explicitly building the entire graph. Store the dictionary in a hash table for O(1) lookups. Starting from beginWord, perform Breadth‑First Search. For each word popped from the queue, iterate through every character position and try replacing it with letters 'a' to 'z'. Each generated candidate word represents a possible transformation. If the word exists in the dictionary and hasn't been visited, push it into the queue and remove it from the set to prevent revisits. Each word can generate up to L * 26 neighbors, and each valid word is processed once, giving overall time complexity O(N * L * 26) with O(N) memory for the queue and visited structure. This method implicitly explores the graph without building it.

Recommended for interviews: The BFS transformation approach is the expected solution. It shows you recognize that the problem is a shortest‑path search in an unweighted graph and that you can generate neighbors dynamically using string manipulation. A brute-force graph build demonstrates understanding of the problem structure, but interviewers typically look for the optimized BFS that combines hashing and on‑the‑fly neighbor generation.

Approach 1: Breadth First Search with Word Transformations

This approach leverages Breadth First Search (BFS), where each word is a node in the graph, and an edge exists between two nodes if they differ by exactly one letter. The goal is to find the shortest path from beginWord to endWord.

Start BFS from the beginWord, exploring transformations by changing each letter and checking if the new word exists in the set of available words. Polished implementation should consider preprocessing the word list for efficient lookup.

Python

from collections import deque

def ladderLength(beginWord, endWord, wordList):
    wordSet = set(wordList)
    if endWord not in wordSet:
        return 0
    q = deque([beginWord])
    ladder = 1

    while q:
        levelSize = len(q)
        for _ in range(levelSize):
            current = q.popleft()
            for i in range(len(current)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    nextWord = current[:i] + c + current[i+1:]
                    if nextWord == endWord:
                        return ladder + 1
                    if nextWord in wordSet:
                        wordSet.remove(nextWord)
                        q.append(nextWord)
        ladder += 1
    return 0

beginWord = "hit"
endWord = "cog"
wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
print(ladderLength(beginWord, endWord, wordList))

Java

import java.util.*;

public class WordLadder {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(endWord)) return 0;
        Queue<String> q = new LinkedList<>();
        q.add(beginWord);
        int ladder = 1;

        while (!q.isEmpty()) {
            int levelSize = q.size();
            for (int i = 0; i < levelSize; i++) {
                String current = q.poll();
                for (int j = 0; j < current.length(); j++) {
                    char[] currArray = current.toCharArray();
                    for (char c = 'a'; c <= 'z'; c++) {
                        currArray[j] = c;
                        String temp = new String(currArray);
                        if (temp.equals(endWord)) return ladder + 1;
                        if (wordSet.contains(temp)) {
                            q.add(temp);
                            wordSet.remove(temp);
                        }
                    }
                }
            }
            ladder++;
        }
        return 0;
    }

    public static void main(String[] args) {
        WordLadder wl = new WordLadder();
        List<String> wordList = Arrays.asList("hot", "dot", "dog", "lot", "log", "cog");
        System.out.println(wl.ladderLength("hit", "cog", wordList));
    }
}

C++

#include <iostream>
#include <vector>
#include <unordered_set>
#include <queue>

using namespace std;

bool oneLetterDifference(const string &s1, const string &s2) {
    int count = 0;
    for (int i = 0; i < s1.length(); ++i) {
        if (s1[i] != s2[i] && ++count > 1) return false;
    }
    return count == 1;
}

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> wordSet(wordList.begin(), wordList.end());
    if (wordSet.find(endWord) == wordSet.end()) return 0;
    queue<string> q;
    q.push(beginWord);
    int ladder = 1;

    while (!q.empty()) {
        int levelSize = q.size();
        for (int i = 0; i < levelSize; ++i) {
            string current = q.front(); q.pop();
            for (int j = 0; j < current.length(); ++j) {
                string temp = current;
                for (char c = 'a'; c <= 'z'; ++c) {
                    temp[j] = c;
                    if (temp == endWord) return ladder + 1;
                    if (wordSet.find(temp) != wordSet.end()) {
                        q.push(temp);
                        wordSet.erase(temp);
                    }
                }
            }
        }
        ladder++;
    }
    return 0;
}

int main() {
    vector<string> wordList = {"hot", "dot", "dog", "lot", "log", "cog"};
    cout << ladderLength("hit", "cog", wordList) << endl;
    return 0;
}

JavaScript

const ladderLength = function(beginWord, endWord, wordList) {
    const wordSet = new Set(wordList);
    if (!wordSet.has(endWord)) return 0;
    let queue = [beginWord];
    let ladder = 1;

    while (queue.length > 0) {
        const levelSize = queue.length;
        for (let i = 0; i < levelSize; i++) {
            const current = queue.shift();
            for (let j = 0; j < current.length; j++) {
                for (let c = 97; c <= 122; c++) {
                    const nextWord = current.substring(0, j) + String.fromCharCode(c) + current.substring(j + 1);
                    if (nextWord === endWord) return ladder + 1;
                    if (wordSet.has(nextWord)) {
                        wordSet.delete(nextWord);
                        queue.push(nextWord);
                    }
                }
            }
        }
        ladder++;
    }
    return 0;
};

const beginWord = "hit";
const endWord = "cog";
const wordList = ["hot", "dot", "dog", "lot", "log", "cog"];

console.log(ladderLength(beginWord, endWord, wordList));

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>

#define MAX_WORDS 5000
#define WORD_LENGTH 10

bool oneLetterDifference(char* word1, char* word2) {
    int count = 0;
    for (int i = 0; i < strlen(word1); i++) {
        if (word1[i] != word2[i]) count++;
        if (count > 1) return false;
    }
    return count == 1;
}

int ladderLength(char *beginWord, char *endWord, char **wordList, int wordListSize) {
    bool visited[MAX_WORDS] = { false };
    char* queue[MAX_WORDS];
    int front = 0, rear = 0;
    int levels = 1;

    queue[rear++] = beginWord;

    while (front < rear) {
        int currLevelSize = rear - front;
        for (int i = 0; i < currLevelSize; i++) {
            char* current = queue[front++];

            if (strcmp(current, endWord) == 0) {
                return levels;
            }

            for (int j = 0; j < wordListSize; j++) {
                if (!visited[j] && oneLetterDifference(current, wordList[j])) {
                    visited[j] = true;
                    queue[rear++] = wordList[j];
                }
            }
        }
        levels++;
    }

    return 0;
}

int main() {
    char* wordList[] = {"hot","dot","dog","lot","log","cog"};
    int wordListSize = sizeof(wordList)/sizeof(wordList[0]);
    printf("%d\n", ladderLength("hit", "cog", wordList, wordListSize));
    return 0;
}

using System;
using System.Collections.Generic;

class WordLadder {
    public int LadderLength(string beginWord, string endWord, IList<string> wordList) {
        HashSet<string> wordSet = new HashSet<string>(wordList);
        if (!wordSet.Contains(endWord)) return 0;
        Queue<string> q = new Queue<string>();
        q.Enqueue(beginWord);
        int ladder = 1;

        while (q.Count > 0) {
            int levelSize = q.Count;
            for (int i = 0; i < levelSize; i++) {
                string current = q.Dequeue();
                char[] currArray = current.ToCharArray();
                for (int j = 0; j < currArray.Length; j++) {
                    for (char c = 'a'; c <= 'z'; c++) {
                        currArray[j] = c;
                        string newWord = new string(currArray);
                        if (newWord.Equals(endWord)) return ladder + 1;
                        if (wordSet.Contains(newWord)) {
                            q.Enqueue(newWord);
                            wordSet.Remove(newWord);
                        }
                    }
                    currArray[j] = current[j];
                }
            }
            ladder++;
        }
        return 0;
    }

    static void Main(string[] args) {
        List<string> wordList = new List<string>() { "hot", "dot", "dog", "lot", "log", "cog" };
        WordLadder wl = new WordLadder();
        Console.WriteLine(wl.LadderLength("hit", "cog", wordList));
    }
}

This Python solution employs BFS utilizing a deque for efficient popping from the front. Each character in a word is replaced to generate transformations. Successful transformations (existing in the word set) are queued. Direct transformation to endWord increases the level count by one, indicating a complete path.

Complexity

Time Complexity: O(N * m^2), with m being word length and N the word count.
Space Complexity: O(N), reflecting the size of the queue and word storage.

Try this approach in the editor

Approach 2: BFS

BFS minimum step model. This problem can be solved with naive BFS, or it can be optimized with bidirectional BFS to reduce the search space and improve efficiency.

Bidirectional BFS is a common optimization method for BFS, with the main implementation ideas as follows:

Create two queues, q1 and q2, for "start -> end" and "end -> start" search directions, respectively.
Create two hash maps, m1 and m2, to record the visited nodes and their corresponding expansion times (steps).
During each search, prioritize the queue with fewer elements for search expansion. If a node visited from the other direction is found during the expansion, it means the shortest path has been found.
If one of the queues is empty, it means that the search in the current direction cannot continue, indicating that the start and end points are not connected, and there is no need to continue the search.

while q1 and q2:
    if len(q1) <= len(q2):
        # Prioritize the queue with fewer elements for expansion
        extend(m1, m2, q1)
    else:
        extend(m2, m1, q2)


def extend(m1, m2, q):
    # New round of expansion
    for _ in range(len(q)):
        p = q.popleft()
        step = m1[p]
        for t in next(p):
            if t in m1:
                # Already visited before
                continue
            if t in m2:
                # The other direction has been searched, indicating that a shortest path has been found
                return step + 1 + m2[t]
            q.append(t)
            m1[t] = step + 1

TypeScript

function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
    if (!wordList.includes(endWord)) return 0;

    const replace = (s: string, i: number, ch: string) => s.slice(0, i) + ch + s.slice(i + 1);
    const { length } = beginWord;
    const words: Record<string, string[]> = {};
    const g: Record<string, string[]> = {};

    for (const w of [beginWord, ...wordList]) {
        const derivatives: string[] = [];

        for (let i = 0; i < length; i++) {
            const nextW = replace(w, i, '*');
            derivatives.push(nextW);

            g[nextW] ??= [];
            g[nextW].push(w);
        }

        words[w] = derivatives;
    }

    let ans = 0;
    let q = words[beginWord];
    const vis = new Set<string>([beginWord]);

    while (q.length) {
        const nextQ: string[] = [];
        ans++;

        for (const variant of q) {
            for (const w of g[variant]) {
                if (w === endWord) return ans + 1;

                if (vis.has(w)) continue;
                vis.add(w);

                nextQ.push(...words[w]);
            }
        }

        q = nextQ;
    }

    return 0;
}

func ladderLength(beginWord string, endWord string, wordList []string) int {
	words := make(map[string]bool)
	for _, word := range wordList {
		words[word] = true
	}
	q := []string{beginWord}
	ans := 1
	for len(q) > 0 {
		ans++
		for i := len(q); i > 0; i-- {
			s := q[0]
			q = q[1:]
			chars := []byte(s)
			for j := 0; j < len(chars); j++ {
				ch := chars[j]
				for k := 'a'; k <= 'z'; k++ {
					chars[j] = byte(k)
					t := string(chars)
					if !words[t] {
						continue
					}
					if t == endWord {
						return ans
					}
					q = append(q, t)
					words[t] = false
				}
				chars[j] = ch
			}
		}
	}
	return 0
}

Try this approach in the editor

Approach 3: Default Approach

func ladderLength(beginWord string, endWord string, wordList []string) int {
	words := make(map[string]bool)
	for _, word := range wordList {
		words[word] = true
	}
	if !words[endWord] {
		return 0
	}

	q1, q2 := []string{beginWord}, []string{endWord}
	m1, m2 := map[string]int{beginWord: 0}, map[string]int{endWord: 0}
	extend := func() int {
		for i := len(q1); i > 0; i-- {
			s := q1[0]
			step, _ := m1[s]
			q1 = q1[1:]
			chars := []byte(s)
			for j := 0; j < len(chars); j++ {
				ch := chars[j]
				for k := 'a'; k <= 'z'; k++ {
					chars[j] = byte(k)
					t := string(chars)
					if !words[t] {
						continue
					}
					if _, ok := m1[t]; ok {
						continue
					}
					if v, ok := m2[t]; ok {
						return step + 1 + v
					}
					q1 = append(q1, t)
					m1[t] = step + 1
				}
				chars[j] = ch
			}
		}
		return -1
	}
	for len(q1) > 0 && len(q2) > 0 {
		if len(q1) > len(q2) {
			m1, m2 = m2, m1
			q1, q2 = q2, q1
		}
		t := extend()
		if t != -1 {
			return t + 1
		}
	}
	return 0
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Breadth First Search with Word Transformations	Time Complexity: O(N * m^2), with m being word length and N the word count. Space Complexity: O(N), reflecting the size of the queue and word storage.
BFS	–
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Explicit Graph Build + BFS	O(N^2 * L)	O(N^2)	Useful for understanding the graph structure or when the dataset is very small
BFS with On‑the‑Fly Word Transformations	O(N * L * 26)	O(N)	General case and interview‑optimal solution for large dictionaries

Frequently asked questions

Is Word Ladder easy or hard?

Word Ladder is classified as Hard on LeetCode because the key insight is recognizing the implicit graph and generating neighbors efficiently. Implementing BFS alone is straightforward, but optimizing neighbor generation and avoiding repeated work makes it challenging.

Word Ladder Python/Java solution

Implement BFS starting from beginWord. Store the word list in a hash set, generate neighbors by replacing each character with 'a'–'z', and push valid transformations into the queue. Track levels to count the transformation length. The same logic works in Python, Java, C++, C#, and JavaScript.

How to solve Word Ladder in O(n)?

A strict O(n) solution is not possible because each word requires generating multiple character transformations. The practical optimal approach is O(N * L * 26) using BFS and a hash set. Each valid word is processed once while generating at most L * 26 candidate transformations.

What is the best approach for Word Ladder?

Breadth-First Search with on-the-fly word transformations is the best approach. Store the dictionary in a hash set and generate neighbors by changing each character to 'a'–'z'. BFS guarantees the shortest transformation path. The complexity is O(N * L * 26) time and O(N) space.

Is Word Ladder asked at Google/Amazon/Meta?

Word Ladder frequently appears in interviews at companies like Amazon, Google, and Meta because it tests graph modeling and BFS traversal. Candidates must recognize that words form nodes in an implicit graph and use BFS to compute the shortest path.

What data structure is used in Word Ladder?

The core data structures are a queue for Breadth-First Search and a hash set for fast dictionary lookups and visited tracking. Strings are manipulated to generate neighbors by changing one character at a time.

What is the time complexity of Word Ladder?

The optimized BFS solution runs in O(N * L * 26) time, where N is the number of words and L is the word length. For each word processed, every position can be replaced with 26 possible characters to generate candidate neighbors. Space complexity is O(N) for the queue and visited set.

Word Ladder solution and explanation

The problem

Approach overview

Approach 1: Breadth First Search with Word Transformations

Approach 2: BFS

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Word Ladder solution and explanation

The problem

Approach overview

Approach 1: Breadth First Search with Word Transformations

Approach 2: BFS

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems