Coding Interview: How Do You Solve Word Ladder with Bidirectional BFS?

Prompt and Applicable Context

Given beginWord, endWord, and wordList, find the length of the shortest transformation sequence. Every adjacent pair must differ in exactly one position, and every word after beginWord, including endWord, must appear in the dictionary. The returned length counts words, not changes.

beginWord = "hit"
endWord   = "cog"
wordList  = ["hot", "dot", "dog", "lot", "log", "cog"]

One shortest sequence:
hit -> hot -> dot -> dog -> cog

Return: 5

Use the standard contract: beginWord and endWord are distinct, all words contain lowercase English letters, every dictionary word has the same length L, dictionary entries are unique, and there are at most N = 5,000 entries. If endWord is absent or unreachable, return 0.

This is a graph question whose graph is hidden inside strings. Each valid word is a vertex; two words share an undirected unit-cost edge when they differ in one position. The prompt therefore asks for a single-pair shortest path in an unweighted graph. Public graph-interview material in 2026 still lists Word Ladder as a BFS transformation problem, and a June 2026 public interview account discusses the harder Word Ladder II variant. Those records establish current preparation value; they do not establish an interview frequency or verified company attribution, so this article makes neither claim.

What the Interviewer Evaluates

The first signal is whether the candidate sees an implicit graph. Comparing every pair of dictionary words builds the right graph, but costs O(N²L) character comparisons. A stronger answer generates only possible neighbors of the current word: replace each of its L characters with the other 25 letters, then use a hash set to test dictionary membership.

The second signal is the shortest-path argument. Every transformation costs one step, so BFS explores states in nondecreasing distance. DFS may eventually find a path but does not make the first path shortest. Dijkstra is correct with unit weights but adds a priority queue without adding information.

The third signal is visited timing. A word must leave the unvisited set when it enters a frontier, not when it is later expanded. Delayed marking lets many parents enqueue the same word, increasing both work and memory. With bidirectional BFS, a generated neighbor must be checked against the opposite current frontier before it is checked against the unvisited set.

The fourth signal is whether the optimization remains provable. Bidirectional BFS keeps one level frontier from each endpoint and expands the smaller frontier. It often reduces a tree-like search from roughly b^d states toward two searches near b^(d/2), where b is effective branching and d is the answer in edges. It does not improve the worst-case asymptotic bound: an adversarial dictionary can still make the algorithm inspect nearly every word.

Finally, a strong answer states the real string cost. Each expanded word tries at most 25L mutations. In Python, creating a candidate string costs O(L), so the implementation is O(NL²) expected time for a fixed 26-letter alphabet, with O(NL) character storage. Calling it O(NL) silently treats string construction as constant time.

Clarifying Questions Before Answering

• What exactly does the return value count? This contract counts both endpoints. A direct valid

transformation therefore returns 2; an edge-count API would return one less.

• Must endWord be in the dictionary? Yes. If it is absent, return 0 before searching. A variant

that allows the target outside the dictionary changes this early-exit rule.

• Are all words the same length and alphabet? Yes: length L, lowercase English letters. Unicode,

mixed lengths, or a larger alphabet changes neighbor generation and its cost.

• Are entries unique? Yes. Converting the input to a set is still useful for expected constant-time

membership and visited removal. If duplicates were allowed, they would not create distinct vertices.

• Do we need one length, one path, or every shortest path? The base problem needs only the length.

Returning a path requires parent maps; returning every shortest path requires preserving all parents from the same BFS level and cannot use the same eager deletion rule unchanged.

• Is this one query or many queries over a stable dictionary? For one query, on-demand mutation is

simple and avoids a full index. Repeated queries may justify a reusable wildcard-pattern index.

• May beginWord already appear in the dictionary? Yes. It is still one vertex and should be removed

from the unvisited set during initialization.

30-Second Answer Framework

“I model each word as a vertex and connect two words when they differ in one position. Every edge costs one transformation, so this is an unweighted shortest-path problem. I would run bidirectional BFS from beginWord and endWord, always expanding the smaller whole-level frontier. For each frontier word, I generate its at most 25L one-letter mutations and test them in a hash set. If a mutation is in the opposite frontier, the two shortest explored prefixes form the shortest sequence, so I return the current word count plus one. Otherwise I remove a valid unseen word as soon as I add it to the next frontier. If endWord is absent or a frontier empties, I return zero. The worst case still visits N words; because Python candidate construction copies L characters, time is O(NL²) and stored string content is O(NL). I would test direct, unreachable, cyclic, duplicate-discovery, and asymmetric-frontier cases.”

Step-by-Step Deep Dive

Start with the graph model. Let the vertex set contain every dictionary word plus beginWord. For any two same-length words, add an edge exactly when their Hamming distance is one. The graph is undirected: if hot can change to dot, the reverse change is also valid. It is unweighted because every legal change contributes one edge.

An explicit pairwise graph compares O(N²) pairs and spends O(L) per comparison. That is O(N²L) preprocessing even when most pairs are unrelated. The input alphabet gives a smaller candidate space. A word has at most 25L distinct one-letter mutations; dictionary membership decides which are real vertices.

One-sided BFS is already correct. Its invariant is:

At the start of level k:
  the frontier contains exactly the discovered words at edge distance k;
  no undiscovered word has distance less than k;
  every word outside unvisited has already been assigned its minimum distance.

BFS creates level k + 1 only from level k. Therefore the first discovery of a word uses a shortest path. Removing a word from unvisited at discovery preserves that fact and prevents duplicate frontier entries.

For a single known target, search from both endpoints. front is one complete level from the begin side, and back is one complete level from the end side. sequence_length equals the sum of their current edge depths plus one, because it counts the frontier words at both ends without a connecting edge yet. Expanding either whole frontier increases that depth sum by one. If a generated word belongs to the opposite frontier, the connecting edge makes the answer sequence_length + 1.

Expanding the smaller frontier changes performance, not correctness. Swapping the two sets only changes which valid BFS layer advances next; each set still represents one exact depth from its own origin. Checking intersection against the opposite current frontier is essential. A single global unvisited set is safe because when a side discovers a word it claims it immediately. If a later expansion had an edge to an already expanded layer of the other search, that earlier expansion would have discovered the same word first, so the searches cannot silently cross behind their current frontiers.

ALPHABET = "abcdefghijklmnopqrstuvwxyz"


def ladder_length(
    begin_word: str,
    end_word: str,
    word_list: list[str],
) -> int:
    unvisited = set(word_list)
    if end_word not in unvisited:
        return 0

    front = {begin_word}
    back = {end_word}
    unvisited.discard(begin_word)
    unvisited.remove(end_word)
    sequence_length = 1

    while front and back:
        if len(front) > len(back):
            front, back = back, front

        next_front: set[str] = set()

        for word in front:
            for index, original in enumerate(word):
                for letter in ALPHABET:
                    if letter == original:
                        continue

                    candidate = word[:index] + letter + word[index + 1 :]

                    if candidate in back:
                        return sequence_length + 1

                    if candidate in unvisited:
                        unvisited.remove(candidate)
                        next_front.add(candidate)

        front = next_front
        sequence_length += 1

    return 0

Trace the sample by frontier layers:

The algorithm expands the smaller cog side at expansion 3. At expansion 4, dot reaches dog or lot reaches log, so it returns 5. Set iteration order may choose a different shortest meeting edge; the length is unchanged.

Let N be dictionary size and L word length. Each word is added to a frontier at most once and, if expanded, tries 25L candidates. Hash lookup is expected O(1), but each Python slice-and-concatenate candidate costs O(L), giving O(NL²) expected worst-case time with a fixed alphabet. The sets store at most O(N) references and their strings contain O(NL) characters. Temporary candidate strings add O(L) at a time. If an interview uses a mutable fixed-width character buffer and treats materializing or hashing a candidate as O(L), the same careful bound still applies.

A wildcard index is the main alternative. Map patterns such as h*t, *ot, and ho* to matching words. It can be reused across many queries and avoids trying letters absent from the dictionary. In Python, creating L pattern strings for N words also costs O(NL²) character work and can retain O(NL) bucket entries. During BFS, clear a consumed pattern bucket or track it as processed; scanning the same large bucket for many words can otherwise recreate quadratic work. For a single query under the stated constraints, mutation plus a set has fewer moving parts.

Test the executable contract, not just the sample:

cases = [
    (
        "hit",
        "cog",
        ["hot", "dot", "dog", "lot", "log", "cog"],
        5,
    ),
    ("hit", "cog", ["hot", "dot", "dog", "lot", "log"], 0),
    ("a", "c", ["a", "b", "c"], 2),
    ("red", "tax", ["ted", "tex", "red", "tax", "tad", "den", "rex", "pee"], 4),
    ("aaa", "bbb", ["aab", "abb", "bbb", "aba", "baa"], 4),
]

for begin_word, end_word, words, expected in cases:
    actual = ladder_length(begin_word, end_word, words)
    assert actual == expected, (begin_word, end_word, actual, expected)

Property tests can generate a small random dictionary, build the explicit pairwise graph as a trusted oracle, and compare its ordinary BFS result with the optimized function. Also keep the input list unchanged, test dictionaries where one frontier grows much faster than the other, and confirm a word reachable through several parents is expanded only once.

High-Quality Sample Answer

“The words form an implicit undirected graph. A vertex is a valid word, and an edge joins words with Hamming distance one. Because all edges cost one, BFS gives the minimum number of transformations. I will return the number of words, so hit -> hot has length two.

I first put the dictionary in a set and reject the case where endWord is absent. I keep one frontier at each endpoint and one set of words that neither search has discovered. On every iteration I expand the smaller complete frontier. For each word and character position, I try the other 25 lowercase letters. I check a candidate against the opposite frontier first; a hit connects two BFS prefixes, so the answer is the accumulated word count plus one. Otherwise, if the candidate is unvisited, I remove it immediately and add it to the next frontier.

The invariant is that each frontier is exactly one distance layer from its endpoint, and every removed word already has its minimum distance from the side that discovered it. Expanding the smaller side does not change those layers. The first frontier connection is shortest because any shorter path would have connected two earlier layers. Immediate removal prevents duplicate discovery.

At most N words are expanded. Each tries 25L mutations, and Python spends O(L) constructing each candidate, so I state O(NL²) expected time and O(NL) stored characters. Bidirectional search usually reduces explored states but has the same worst case. For repeated queries I would consider a reusable wildcard index; for this one-shot query, mutation is simpler. I would verify the official sample, missing target, direct transformation, several shortest routes, cycles, and a random explicit-graph oracle.”

Common Mistakes

• Running DFS and returning its first path → DFS does not visit paths by transformation count →

Use BFS because every edge has unit cost.

• Comparing every dictionary pair → graph construction costs O(N²L) → **Generate at most 25L

candidate neighbors per expanded word.**

• Marking a word visited only when popped → several parents can enqueue it → **Remove it from

unvisited when adding it to a frontier.**

• Checking only unvisited before the opposite frontier → the meeting word has already been removed

by the other search → Test the opposite current frontier first.

• Expanding whichever side is named front → one side may explode while the other stays small →

Swap and expand the smaller whole-level frontier.

• Mixing edge count with word count → the sample returns four instead of five → **Initialize the

sequence count to one and add the connecting word on a meeting edge.**

• Claiming bidirectional BFS changes the worst-case complexity → a dense adversarial dictionary may

still expose nearly every word → Describe the branching-factor benefit as typical, not guaranteed.

• Calling Python mutation O(NL) → every candidate copies or hashes L characters → **State the

string-operation model and use O(NL²) for this implementation.**

• Reusing wildcard buckets without consuming them → the same large list is scanned repeatedly →

Clear each processed pattern bucket or mark it consumed.

• Using one global visited set but allowing partial-level expansion → meeting order and distance

accounting become hard to prove → Advance a complete frontier level at a time.

• Citing a self-reported company experience as verified attribution → a public post is not an

employer record → Keep companyName null and use the record only as current public evidence.

Follow-Ups and How to Handle Them

Follow-up 1: How would you return one actual shortest sequence?

Keep a parent map for each direction. When a candidate is discovered, record the word that produced it. At the meeting edge, walk the begin-side parent map back to beginWord, reverse that prefix, then walk the end-side parent map toward endWord. Because the implementation can swap frontier variables, store parent maps by semantic direction rather than assuming the current front is always the begin side. Parent storage is O(N) references in addition to the dictionary strings.

Follow-up 2: What changes for Word Ladder II, which returns every shortest sequence?

One parent per word is insufficient. Ordinary level-order BFS is often easier to reason about: collect every predecessor that reaches a word at its minimum level, and remove newly discovered words from the global dictionary only after the whole level finishes. That permits multiple same-level parents without letting longer paths add parents later. Stop after completing the first level that reaches endWord, then backtrack through the predecessor DAG. Output size can be exponential, so complexity must include the total number and length of returned sequences.

Follow-up 3: When is ordinary one-sided BFS preferable?

Use it when the dictionary is small, only one endpoint is known, the graph is directed and reverse neighbors are expensive, or code simplicity matters more than reducing the frontier. One-sided BFS has fewer invariants and makes parent reconstruction straightforward. It retains the same neighbor generator and the same O(NL²) bound for this Python representation.

Follow-up 4: When would you build wildcard-pattern buckets?

Build them when many queries share a stable dictionary, the alphabet is large, or generating every alphabet substitution wastes work. Version the index with the dictionary, include beginWord patterns per query when it is not indexed, and consume each bucket at most once per search. The trade-off is preprocessing time, bucket memory, and invalidation when words change.

Follow-up 5: What if different letter changes have different costs?

The graph becomes weighted, so BFS layers no longer represent minimum cost. Use Dijkstra for nonnegative costs, generating the same implicit neighbors but ordering the frontier by accumulated cost. A valid admissible heuristic may support A*, but Hamming distance is admissible only after scaling by a proven lower bound on the cost of any remaining character change.

Follow-up 6: What if the alphabet is Unicode or words have different lengths?

Define legal operations first. Unicode code points and grapheme clusters are different units, and insert or delete operations introduce length-changing edges. Direct substitution generation no longer covers the graph. Depending on the contract, use an indexed edit-distance-one neighbor search, a trie, or length-and-pattern buckets, and include normalization rules in equality and hashing.

Follow-up 7: How would you prove the bidirectional stop condition in an interview?

Assign each current frontier a depth from its own endpoint. The algorithm advances exactly one complete depth layer per iteration. Before an expansion, sequence_length is the two frontier depths plus one. A generated edge into the opposite frontier therefore forms a path with sequence_length + 1 words. If a shorter path existed, it would contain an edge between two layers with a smaller depth sum, and those layers would already have been expanded and connected. That contradicts this being the first frontier meeting.

Follow-up 8: How would you validate the optimized search beyond examples?

For small random dictionaries, explicitly connect every pair whose Hamming distance is one and run a plain BFS oracle. Compare the answer with bidirectional BFS across thousands of generated cases. Add invariants that neither frontier intersects unvisited, no word is discovered twice, and every next frontier word differs by one character from a current frontier word. This separates correctness evidence from a few hand-picked outputs.