Word Ladder

Approach Summary

BFS where each step transforms one character. Use a word set for O(1) neighbor lookup. BFS guarantees shortest path.

Full Solution & Approach

Each transformation changes exactly one character, so the words form a graph where edges connect words differing by one letter, and the answer is the shortest path from beginWord to endWord — BFS. Put the word list in a set for O(1) membership checks. BFS from beginWord; at each word, generate every one-letter variant by substituting each of 26 letters at each position, and if a variant is in the word set and unvisited, enqueue it with the next step count. The step count is incremented per BFS level, which is exactly the transformation length. The branching factor is bounded by word_length × 26, so the total work is O(n · m² · 26) in the worst case. Because BFS explores by distance, the first time endWord is reached is guaranteed to be the minimum number of transformations.

BFS visits at most every word once, expanding each into m × 26 candidates checked in O(m) — O(n · m² · 26) worst case. The visited set and queue hold up to n words — O(n · m).

Solution Code

Solution

from collections import deque

def ladder_length(begin_word: str, end_word: str, word_list: list[str]) -> int:
    words = set(word_list)
    if begin_word == end_word:
        return 0
    if end_word not in words:
        return 0
    queue = deque([(begin_word, 1)])
    visited = {begin_word}
    while queue:
        word, steps = queue.popleft()
        if word == end_word:
            return steps
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                nxt = word[:i] + c + word[i + 1:]
                if nxt in words and nxt not in visited:
                    visited.add(nxt)
                    queue.append((nxt, steps + 1))
    return 0

function ladderLength(beginWord, endWord, wordList) {
  const words = new Set(wordList);
  if (beginWord === endWord) return 0;
  if (!words.has(endWord)) return 0;
  const queue = [[beginWord, 1]];
  const visited = new Set([beginWord]);
  const alphabet = 'abcdefghijklmnopqrstuvwxyz';
  for (let qi = 0; qi < queue.length; qi++) {
    const [word, steps] = queue[qi];
    if (word === endWord) return steps;
    for (let i = 0; i < word.length; i++) {
      for (const c of alphabet) {
        const next = word.slice(0, i) + c + word.slice(i + 1);
        if (words.has(next) && !visited.has(next)) {
          visited.add(next);
          queue.push([next, steps + 1]);
        }
      }
    }
  }
  return 0;
}

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Set<String> words = new HashSet<>(wordList);
    if (beginWord.equals(endWord)) return 0;
    if (!words.contains(endWord)) return 0;
    Deque<Object[]> queue = new ArrayDeque<>();
    queue.offer(new Object[]{beginWord, 1});
    Set<String> visited = new HashSet<>();
    visited.add(beginWord);
    while (!queue.isEmpty()) {
        Object[] entry = queue.poll();
        String word = (String) entry[0];
        int steps = (int) entry[1];
        if (word.equals(endWord)) return steps;
        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.contains(next) && !visited.contains(next)) {
                    visited.add(next);
                    queue.offer(new Object[]{next, steps + 1});
                }
            }
            chars[i] = original;
        }
    }
    return 0;
}

int ladderLength(const string& beginWord, const string& endWord, const vector<string>& wordList) {
    unordered_set<string> words(wordList.begin(), wordList.end());
    if (beginWord == endWord) return 0;
    if (!words.count(endWord)) return 0;
    queue<pair<string,int>> q;
    q.push({beginWord, 1});
    unordered_set<string> visited;
    visited.insert(beginWord);
    while (!q.empty()) {
        auto [word, steps] = q.front(); q.pop();
        if (word == endWord) return steps;
        for (int i = 0; i < (int)word.size(); i++) {
            string next = word;
            for (char c = 'a'; c <= 'z'; c++) {
                next[i] = c;
                if (words.count(next) && !visited.count(next)) {
                    visited.insert(next);
                    q.push({next, steps + 1});
                }
            }
        }
    }
    return 0;
}

Edge Cases to Watch

beginWord equals endWord — return 0
endWord not in the word list — return 0
No path exists — return 0
Words of length 1 — the branching factor is tiny and the search is fast

How to Recognize This Pattern

Shortest transformation sequence
One character change per step

Complexity Analysis

Time Complexity

O(n · m² · 26)

Space Complexity

O(n · m)