Word Ladder

Problem Statement

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

You must change exactly one letter in each transformation, and each transformed word must exist in the word list.

What to notice first

• This is a shortest path problem on an implicit graph.
• Two words are connected if they differ by exactly one letter.
• BFS finds the shortest path.
• Bidirectional BFS can halve the search space.

Examples

beginWord	endWord	wordList	Output	Explanation
”hit"	"cog”	[“hot”,“dot”,“dog”,“lot”,“log”,“cog”]	5	Path: hit → hot → dot → dog → cog (5 words total)
“hit"	"cog”	[“hot”,“dot”,“dog”,“lot”,“log”]	0	No path to “cog” exists
”hot"	"dog”	[“hot”,“dog”,“dot”]	3	Path: hot → dot → dog (3 words)

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

Real-World Applications

Where this pattern appears

• Social network analysis and friend recommendations
• Route planning and GPS navigation
• Dependency resolution and build systems
• Recommendation systems and collaborative filtering

Complexity Comparison

Approach	Time	Space
BFS	O(n*L^2)	O(n*L)
Bidirectional BFS	O(n*L^2)	O(n*L)

Approach 1: BFS

★ Recommended

⏱ Time O(n*L^2) 💾 Space O(n*L)

Python

word_ladder_bfs.py

from collections import deque

def ladderLength(beginWord, endWord, wordList):
    """BFS to find shortest transformation sequence."""
    wordSet = set(wordList)
    if endWord not in wordSet:
        return 0

    queue = deque([(beginWord, 1)])
    visited = {beginWord}

    while queue:
        word, length = queue.popleft()
        if word == endWord:
            return length

        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                if c != word[i]:
                    new_word = word[:i] + c + word[i+1:]
                    if new_word in wordSet and new_word not in visited:
                        visited.add(new_word)
                        queue.append((new_word, length + 1))

    return 0

C++

word_ladder_bfs.cpp

int main() { return 0; }

Java

WordLadderBFS.java

import java.util.*;

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(endWord)) return 0;

        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.offer(beginWord);
        visited.add(beginWord);

        int length = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String word = queue.poll();
                if (word.equals(endWord)) return length;

                char[] arr = word.toCharArray();
                for (int j = 0; j < arr.length; j++) {
                    char old = arr[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c != old) {
                            arr[j] = c;
                            String newWord = new String(arr);
                            if (wordSet.contains(newWord) && !visited.contains(newWord)) {
                                visited.add(newWord);
                                queue.offer(newWord);
                            }
                        }
                    }
                    arr[j] = old;
                }
            }
            length++;
        }
        return 0;
    }
}

JavaScript

word_ladder_bfs.js

function solution() { return 0; }
module.exports = solution;

Rust

word_ladder_bfs.rs

pub fn solution() -> i32 { 0 }

Go

word_ladder_bfs.go

package main
func solution() int { return 0 }

Approach 2: Bidirectional BFS

✓ Simple

⏱ Time O(n*L^2) 💾 Space O(n*L)

Python

word_ladder_bidirectional_bfs.py

from collections import deque

def ladderLength(beginWord, endWord, wordList):
    """Bidirectional BFS for more efficient search."""
    wordSet = set(wordList)
    if endWord not in wordSet:
        return 0

    begin_queue, end_queue = deque([beginWord]), deque([endWord])
    begin_visited, end_visited = {beginWord}, {endWord}
    length = 1

    while begin_queue or end_queue:
        length += expand(begin_queue, begin_visited, end_visited, wordSet)
        if begin_visited & end_visited:
            return length
        length += expand(end_queue, end_visited, begin_visited, wordSet)
        if begin_visited & end_visited:
            return length

    return 0

def expand(queue, visited, other_visited, wordSet):
    if not queue:
        return 0

    for _ in range(len(queue)):
        word = queue.popleft()
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                if c != word[i]:
                    new_word = word[:i] + c + word[i+1:]
                    if new_word in other_visited:
                        return 1
                    if new_word in wordSet and new_word not in visited:
                        visited.add(new_word)
                        queue.append(new_word)
    return 0

C++

word_ladder_bidirectional_bfs.cpp

class Solution {
    // TODO: Implement
};

Java

WordLadderBidirectionalBFS.java

import java.util.*;

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(endWord)) return 0;

        Set<String> beginSet = new HashSet<>(), endSet = new HashSet<>();
        beginSet.add(beginWord);
        endSet.add(endWord);

        return bfs(beginSet, endSet, wordSet, 1);
    }

    private int bfs(Set<String> beginSet, Set<String> endSet, Set<String> wordSet, int length) {
        if (beginSet.isEmpty()) return 0;
        if (beginSet.size() > endSet.size()) {
            return bfs(endSet, beginSet, wordSet, length);
        }

        wordSet.removeAll(beginSet);
        Set<String> nextLevel = new HashSet<>();

        for (String word : beginSet) {
            char[] arr = word.toCharArray();
            for (int i = 0; i < arr.length; i++) {
                char old = arr[i];
                for (char c = 'a'; c <= 'z'; c++) {
                    if (c != old) {
                        arr[i] = c;
                        String newWord = new String(arr);
                        if (endSet.contains(newWord)) return length + 1;
                        if (wordSet.contains(newWord)) nextLevel.add(newWord);
                    }
                }
                arr[i] = old;
            }
        }

        return bfs(nextLevel, endSet, wordSet, length + 1);
    }
}

JavaScript

word_ladder_bidirectional_bfs.js

// Graph solution implementation
function solve() {
    // TODO: Implement
}

Rust

word_ladder_bidirectional_bfs.rs

impl Solution {
    // TODO: Implement
}

pub struct Solution;

Go

word_ladder_bidirectional_bfs.go

package main

// TODO: Implement solution

Interview Tips

Key trade-offs to discuss

• Time vs. space trade-offs between approaches
• Handling edge cases (empty inputs, single elements, duplicates)
• Optimization opportunities and when they matter
• Follow-up variations and constraint changes

← Previous
#433 Minimum Genetic Mutation