Word Ladder

hardGraphs: Topological Sort & Union-Find421 stepsJava · Python · C++

Find the fewest words to go from beginWord to endWord, changing one letter at a time, using only words in the list. Each word is a node; BFS from the start finds the shortest path. Neighbours come from trying all 26 letters at every position.

▶ Watch the animated trace

Traced input: beginWord = hit, endWord = cog, wordList = [hot, dot, dog, lot, log, cog] → 5. Original problem: neetcode.io/problems/word-ladder

Complexity

BestO(N·L·26)

AverageO(N·L·26)

WorstO(N·L·26)

SpaceO(N)

N words of length L; each word generates L·26 candidates.

Key idea

Shortest number of steps in an unweighted graph = BFS.
Generate neighbours by mutating one letter instead of comparing every pair of words.
Remove words from the set when queued so they're never visited twice.
The answer counts words, so the start is level 1.

Common mistakes

Forgetting that endWord must be in the list.
Comparing every pair of words to build the graph is O(N²·L).
Off-by-one: the count includes both the first and last word.

Solution

Java

int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Set<String> words = new HashSet<>(wordList);
    if (!words.contains(endWord)) {
        return 0;
    }
    Queue<String> queue = new ArrayDeque<>();
    queue.offer(beginWord);
    words.remove(beginWord);
    int level = 1;
    while (!queue.isEmpty()) {
        for (int size = queue.size(); size > 0; size--) {
            char[] w = queue.poll().toCharArray();
            for (int i = 0; i < w.length; i++) {
                char orig = w[i];
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    w[i] = ch;
                    String next = new String(w);
                    if (next.equals(endWord)) {
                        return level + 1;
                    }
                    if (words.remove(next)) {
                        queue.offer(next);
                    }
                }
                w[i] = orig;
            }
        }
        level++;
    }
    return 0;
}

Python

def ladderLength(beginWord: str, endWord: str, wordList: List[str]) -> int:
    words = set(wordList)
    if endWord not in words:
        return 0
    queue = deque([beginWord])
    words.discard(beginWord)
    level = 1
    while queue:
        for _ in range(len(queue)):
            w = queue.popleft()
            for i in range(len(w)):
                for ch in "abcdefghijklmnopqrstuvwxyz":
                    nxt = w[:i] + ch + w[i + 1:]
                    if nxt == endWord:
                        return level + 1
                    if nxt in words:
                        words.remove(nxt)
                        queue.append(nxt)
        level += 1
    return 0

C++

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> words(wordList.begin(), wordList.end());
    if (!words.count(endWord)) {
        return 0;
    }
    queue<string> q;
    q.push(beginWord);
    words.erase(beginWord);
    int level = 1;
    while (!q.empty()) {
        for (int size = q.size(); size > 0; size--) {
            string w = q.front(); q.pop();
            for (size_t i = 0; i < w.size(); i++) {
                char orig = w[i];
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    w[i] = ch;
                    if (w == endWord) {
                        return level + 1;
                    }
                    if (words.erase(w)) {
                        q.push(w);
                    }
                }
                w[i] = orig;
            }
        }
        level++;
    }
    return 0;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
End word missing cog is not in the list.	`beginWord = hit, endWord = cog, wordList = [hot, dot, dog, lot, log]`	`0`
One step a → c directly.	`beginWord = a, endWord = c, wordList = [a, b, c]`	`2`
Disconnected hot and dog differ in two letters with nothing in between.	`beginWord = hot, endWord = dog, wordList = [dog]`	`0`