Word Ladder: BFS changing one letter at a time

• Word Ladder models words as graph nodes connected by edges when they differ by exactly one letter.
• BFS from the begin word explores by distance, so the first arrival at the end word is the shortest transformation sequence.
• Neighbor generation tries every single-letter substitution at each position and keeps only dictionary words.
• HashSet for the dictionary enables O(1) membership checks, avoiding quadratic pair-wise comparison.
• Time is O(N * L * 26); space is O(N) for the dictionary and visited sets.

What is the Word Ladder problem?

Given a begin word, an end word, and a dictionary of equal-length words, find the length of the shortest transformation sequence from begin to end. Each step changes exactly one letter, and every intermediate word must exist in the dictionary. If no transformation exists, return 0.

package com.bank.service;

import java.util.*;

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

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

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                String word = queue.poll();
                char[] chars = word.toCharArray();
                for (int j = 0; j < chars.length; j++) {
                    char original = chars[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == original) continue;
                        chars[j] = c;
                        String candidate = new String(chars);
                        if (candidate.equals(endWord)) {
                            return level + 1;
                        }
                        if (dict.contains(candidate)
                                && visited.add(candidate)) {
                            queue.offer(candidate);
                        }
                    }
                    chars[j] = original;
                }
            }
            level++;
        }
        return 0;
    }
}

Why model this as a graph problem?

Each word is a node. Two words are connected by an edge if they differ by exactly one letter. The shortest transformation sequence is the shortest path in this implicit graph. Since all edges have equal weight (one step), BFS finds the shortest path.

hit → hot → dot → dog → cog

Graph (partial):
  hit --- hot --- dot --- dog --- cog
            \                /
             lot --- log ---+

BFS from "hit":
  Level 1: [hit]
  Level 2: [hot]
  Level 3: [dot, lot]
  Level 4: [dog, log]
  Level 5: [cog] ← found! length = 5

Why generate neighbors by substitution rather than comparing all pairs?

Comparing every pair of words to find one-letter differences is O(N^2 * L), which is too slow for large dictionaries. Generating neighbors by trying all 26 letters at each position is O(L * 26) per word, and checking each candidate against the HashSet is O(1). This is dramatically faster.

// SLOW: compare all pairs O(N^2 * L)
for (String a : dict) {
    for (String b : dict) {
        if (differByOne(a, b)) addEdge(a, b);
    }
}

// FAST: generate neighbors O(L * 26) per word
for (int j = 0; j < chars.length; j++) {
    for (char c = 'a'; c <= 'z'; c++) {
        // try substitution and check dict
    }
}

How does level-by-level BFS track the distance?

At the start of each BFS level, record the queue size. Process exactly that many words, generating their neighbors. After processing one level, increment the distance counter. When the end word is generated as a neighbor, the current level plus one is the answer.

What is bidirectional BFS?

Bidirectional BFS starts from both the begin word and the end word simultaneously, expanding the smaller frontier at each step. The two frontiers meet in the middle, reducing the search space from O(b^d) to O(b^(d/2)) where b is the branching factor and d is the distance.

// Bidirectional BFS sketch
Set<String> frontBegin = new HashSet<>();
Set<String> frontEnd = new HashSet<>();
frontBegin.add(beginWord);
frontEnd.add(endWord);
int level = 1;

while (!frontBegin.isEmpty() && !frontEnd.isEmpty()) {
    // Always expand the smaller frontier
    if (frontBegin.size() > frontEnd.size()) {
        Set<String> temp = frontBegin;
        frontBegin = frontEnd;
        frontEnd = temp;
    }
    Set<String> nextFront = new HashSet<>();
    for (String word : frontBegin) {
        // Generate neighbors
        // If neighbor is in frontEnd, return level + 1
        // Else add to nextFront
    }
    frontBegin = nextFront;
    level++;
}

What are edge cases?

• End word not in dictionary: return 0 immediately.
• Begin word equals end word: return 1 (or 0 depending on the problem definition).
• No transformation path exists: BFS exhausts the queue and returns 0.
• Begin word not in dictionary: that is fine, it is the starting point, not an intermediate word.

// Edge case: end word not in dictionary
if (!dict.contains(endWord)) return 0;  // early exit

// Edge case: begin word is the end word
// Some problem statements say return 0, others say return 1
// Clarify with the interviewer

What are common mistakes?

The first mistake is building the full adjacency list upfront by comparing all pairs, which is O(N^2 * L). The second mistake is forgetting to mark visited at enqueue time, causing the same word to be enqueued from multiple neighbors. The third mistake is not handling the case where the end word is not in the dictionary.

// WRONG: mark visited at dequeue time
String word = queue.poll();
visited.add(word);  // too late, may already be in queue multiple times

// CORRECT: mark visited at enqueue time
if (visited.add(candidate)) {
    queue.offer(candidate);
}

What is the time and space complexity?

Time: O(N * L * 26) where N is the dictionary size and L is the word length. Each word is dequeued once, and for each word you try L positions with 26 letters each, checking a HashSet in O(L) time (for hashing the string). Space: O(N) for the dictionary, visited set, and queue.

What should a senior engineer know?

At the National Bank of India, account-status codes sometimes had to migrate to a target code one character at a time, with every intermediate code required to be an approved valid code. BFS over single-letter substitutions checked against the approved-code set gave the shortest migration path. For large code sets, bidirectional BFS from both ends cut the search space dramatically.