Word Ladder

Hard Problem 109 of 151 Java and Python

Problem

A transformation sequence from beginWord to endWord changes one letter at a time, and every intermediate word must be in wordList. (beginWord does not need to be in the list.)

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

Example 1

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

Example 2

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

Constraints

1 ≤ word length ≤ 10
1 ≤ wordList.length ≤ 5000
All words are lowercase and the same length.

Explanation

Words are nodes; two words are connected if they differ by one letter. "Shortest sequence" in an unweighted graph means BFS from beginWord.

Finding neighbours by comparing against every word costs O(N · L) per word. It is faster to try all 26 letters at each position and look the result up in a set: O(26 · L) per word.

Approach 1 · Better

BFS, compare with every word

Time O(N² · L)
Space O(N)

BFS from beginWord; neighbours are unvisited list words that differ in exactly one position.

Queue (beginWord, 1).
Pop a word; if it is endWord, return its length.
For every unvisited word in the list that differs by one letter, mark it and enqueue with length + 1.

Java

import java.util.*;

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        boolean[] used = new boolean[wordList.size()];
        Deque<String> queue = new ArrayDeque<>();
        queue.add(beginWord);
        for (int length = 1; !queue.isEmpty(); length++) {
            for (int k = queue.size(); k > 0; k--) {
                String word = queue.poll();
                if (word.equals(endWord)) {
                    return length;
                }
                for (int i = 0; i < wordList.size(); i++) {
                    if (!used[i] && oneApart(word, wordList.get(i))) {
                        used[i] = true;
                        queue.add(wordList.get(i));
                    }
                }
            }
        }
        return 0;
    }

    private boolean oneApart(String a, String b) {
        int diff = 0;
        for (int i = 0; i < a.length() && diff < 2; i++) {
            if (a.charAt(i) != b.charAt(i)) {
                diff++;
            }
        }
        return diff == 1;
    }
}

Python

from collections import deque

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        used = [False] * len(wordList)
        queue = deque([(beginWord, 1)])
        while queue:
            word, length = queue.popleft()
            if word == endWord:
                return length
            for i, other in enumerate(wordList):
                if not used[i] and sum(a != b for a, b in zip(word, other)) == 1:
                    used[i] = True
                    queue.append((other, length + 1))
        return 0

Approach 2 · Optimal

BFS, generate neighbours letter by letter

Time O(N · L · 26)
Space O(N · L)

Keep the word list in a set. For each word, try every letter at every position; any result in the set is a neighbour (remove it from the set to mark it visited).

Put wordList in a set; if endWord is missing, return 0.
BFS by levels from beginWord.
For each word, for each position and letter a–z, build the candidate; if it is in the set, remove it and enqueue it.

Java

import java.util.*;

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> words = new HashSet<>(wordList);
        if (!words.contains(endWord)) {
            return 0;
        }
        Deque<String> queue = new ArrayDeque<>();
        queue.add(beginWord);
        for (int length = 1; !queue.isEmpty(); length++) {
            for (int k = queue.size(); k > 0; k--) {
                String word = queue.poll();
                if (word.equals(endWord)) {
                    return length;
                }
                char[] chars = word.toCharArray();
                for (int i = 0; i < chars.length; i++) {
                    char original = chars[i];
                    for (char c = 'a'; c <= 'z'; c++) {
                        chars[i] = c;
                        String next = new String(chars);
                        if (words.remove(next)) {
                            queue.add(next);
                        }
                    }
                    chars[i] = original;
                }
            }
        }
        return 0;
    }
}

Python

from collections import deque
from string import ascii_lowercase

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        words = set(wordList)
        if endWord not in words:
            return 0
        queue = deque([(beginWord, 1)])
        while queue:
            word, length = queue.popleft()
            if word == endWord:
                return length
            for i in range(len(word)):
                for c in ascii_lowercase:
                    nxt = word[:i] + c + word[i + 1:]
                    if nxt in words:
                        words.remove(nxt)
                        queue.append((nxt, length + 1))
        return 0

Complexity compared

Approach	Time	Space
Better BFS, compare with every word	O(N² · L)	O(N)
Optimal BFS, generate neighbours letter by letter	O(N · L · 26)	O(N · L)

Key takeaways

Shortest path with equal-cost steps → BFS. Bidirectional BFS (from both ends) roughly halves the search depth.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem