Problem statement

A transformation sequence from beginWord to endWord is a chain of words where every adjacent pair differs by exactly one letter and every word after the first appears in wordList.

Return the number of words in the shortest such sequence, or 0 if none exists.

Example 1

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5

Example 2

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: endWord is not in wordList.

Example 3

Input: beginWord = "a", endWord = "c", wordList = ["a","b","c"]
Output: 2

Constraints

• 1 <= beginWord.length <= 6
• All words have the same length.
• 1 <= wordList.length <= 20
• beginWord != endWord
• All words consist of lowercase English letters.

Hints for Word Ladder

1. Hint 1

   Every transformation costs the same, so breadth-first search finds the shortest chain.

2. Hint 2

   Expand a word to every unused list entry that differs from it in exactly one position.

3. Hint 3

   Count words rather than steps: the answer is one more than the number of transformations.

How to solve Word Ladder

BFS over words where an edge is a one-letter difference; the level count is the number of words in the chain.

Approach

1. Frontier = [beginWord], level = 1.
2. Expand each word to unused list entries with exactly one differing position; return level + 1 on reaching endWord.
3. Return 0 if exhausted.

Why it works

Uniform edge cost makes BFS optimal, and counting levels from 1 yields the number of words rather than transformations.

Complexity

• Time — O(levels · |list| · L)
• Space — O(|list|)

Pitfalls

• For large lists, generate the 26 · L neighbours of each word and look them up in a set instead of scanning the list.

Reference solution

Python

def ladderLength(beginWord: str, endWord: str, wordList) -> int:
    used = [False] * len(wordList)
    frontier = [beginWord]
    level = 1
    while frontier:
        nxt = []
        for word in frontier:
            for i, candidate in enumerate(wordList):
                if used[i]:
                    continue
                diff = sum(1 for a, b in zip(candidate, word) if a != b)
                if diff != 1:
                    continue
                if candidate == endWord:
                    return level + 1
                used[i] = True
                nxt.append(candidate)
        frontier = nxt
        level += 1
    return 0

Java

public static int ladderLength(String beginWord, String endWord, String[] wordList) {
    boolean[] used = new boolean[wordList.length];
    List<String> frontier = new ArrayList<>();
    frontier.add(beginWord);
    int level = 1;
    while (!frontier.isEmpty()) {
        List<String> next = new ArrayList<>();
        for (String word : frontier) {
            for (int i = 0; i < wordList.length; i++) {
                if (used[i]) continue;
                int diff = 0;
                for (int k = 0; k < wordList[i].length(); k++) {
                    if (wordList[i].charAt(k) != word.charAt(k)) diff++;
                }
                if (diff != 1) continue;
                if (wordList[i].equals(endWord)) return level + 1;
                used[i] = true;
                next.add(wordList[i]);
            }
        }
        frontier = next;
        level++;
    }
    return 0;
}

C++

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    vector<bool> used(wordList.size(), false);
    vector<string> frontier;
    frontier.push_back(beginWord);
    int level = 1;
    while (!frontier.empty()) {
        vector<string> next;
        for (const string& word : frontier) {
            for (size_t i = 0; i < wordList.size(); i++) {
                if (used[i]) continue;
                int diff = 0;
                for (size_t k = 0; k < wordList[i].size(); k++) {
                    if (wordList[i][k] != word[k]) diff++;
                }
                if (diff != 1) continue;
                if (wordList[i] == endWord) return level + 1;
                used[i] = true;
                next.push_back(wordList[i]);
            }
        }
        frontier = next;
        level++;
    }
    return 0;
}

JavaScript

var ladderLength = function(beginWord, endWord, wordList) {
    const used = wordList.map(function() { return false; });
    let frontier = [beginWord];
    let level = 1;
    while (frontier.length > 0) {
        const next = [];
        for (let f = 0; f < frontier.length; f++) {
            for (let i = 0; i < wordList.length; i++) {
                if (used[i]) continue;
                let diff = 0;
                for (let k = 0; k < wordList[i].length; k++) {
                    if (wordList[i].charAt(k) !== frontier[f].charAt(k)) diff++;
                }
                if (diff !== 1) continue;
                if (wordList[i] === endWord) return level + 1;
                used[i] = true;
                next.push(wordList[i]);
            }
        }
        frontier = next;
        level++;
    }
    return 0;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Design Movie Rental System Hard
• Dinner Plate Stacks Hard
• Prefix and Suffix Search Hard
• LFU Cache Hard
• Vertical Order Traversal of a Binary Tree Hard
• Maximum Number of Ways to Partition an Array Hard