What is a shortest path ladder, and how do you solve one?

In this article

1. Before you start
2. Why interviewers ask this
3. Shortest path ladder from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page is one step of the coding interview patterns learning path.

Why interviewers ask this

A ladder problem separates candidates who recognize a graph hiding inside a puzzle from candidates who try to search it by hand. Nothing in the statement of Word Ladder says "graph", so the question tests whether you model it before you code it.

Candidates report seeing Word Ladder, a lock-opening variant and a "shortest path between connections" question in senior and staff coding rounds, usually with follow-ups. These are candidate reports, not published statements by any company.

A weak answer tries recursion over all word orders and runs out of time. A strong answer names the graph, uses BFS, and counts the result correctly. A Staff-level answer also says how neighbors are found quickly, what changes when the same data is queried many times, and when BFS stops being the right tool.

Shortest path ladder from first principles

Shortest path ladder

A shortest path ladder is a search problem in which each state is a node and each allowed one-step change joins two states with an edge, so the answer is the fewest steps, a fewest-edges path, from a start state to a goal state.

Wildcard bucket

A wildcard bucket is a list of every word that matches one pattern with a single letter replaced by a star, such as h*t, so the words one letter apart from a given word are found by lookup instead of by comparing pairs.

In plain words

Think of a staircase where every landing is a word and you may only step to a word that differs by one letter. You want the fewest landings between two words. The analogy breaks in one place: a real staircase has a fixed shape, while here the shape is built from the dictionary you are given.

"Shortest path ladder" is a working name used on this page, not a standard textbook term. The technique behind it is standard. Breadth-first search is a graph search that visits nodes in order of their distance, in edges, from the start. When every edge counts the same, it finds the fewest-edge path to every reachable node. Its running time is proportional to nodes plus edges (Sedgewick and Wayne; cp-algorithms).

In one precise sentence: model the states as a graph, then run BFS from the start until the goal is reached.

Step 1: Treat each word as a node and each one-letter change as an edge

The Word Ladder statement on LeetCode defines a transformation sequence as a chain of words in which every adjacent pair differs by a single letter, every word after the first is in the word list, and the chain ends at the end word. The beginning word does not need to be in the list. The task is to return the number of words in the shortest such sequence, or 0 if none exists.

Input: a begin word, an end word and a dictionary. Output: a graph you never draw in full, whose nodes are words and whose edges join words one letter apart. Note the counting rule: the answer counts words, so a path of four edges returns 5.¹ The same node-and-edge model underlies topological sort and cycle detection in a directed graph, which use different searches on it. You now have the model; the next step makes its edges cheap to find.

Step 2: Find neighbors with wildcard buckets

The slow way to find a word's neighbors compares it with every other word. For 5,000 words, the limit in the problem's constraints, that is 12,497,500 pair comparisons.¹ The fast way builds an index once. For each word and each position, replace that letter with a star and file the word under the resulting pattern. The word hot goes under *ot, h*t and ho*.

Two words are one letter apart exactly when they share a pattern. To list a word's neighbors, build its patterns and read those buckets. For 5,000 words of length 10, the index holds at most 50,000 entries.¹ A Python defaultdict(list) is the natural container (see defaultdict in Python).

Step 3: Explore level by level with a queue

A queue holds the frontier. Start with the begin word at distance 1. Repeatedly take the oldest word from the queue, read its neighbors from the buckets, and add each neighbor you have not seen, recording its distance as one more than the current word's. Because the oldest word is always taken first, all words at distance 2 are expanded before any at distance 3. In short, a queue explores a graph level by level.

Mark a word as seen when you add it to the queue, not when you take it out. Otherwise the same word can be added many times before it is processed. In Python, a deque (a double-ended queue) removes items from the left end in constant time (Python documentation); list.pop(0) shifts every remaining item and is the common slow choice.

Step 4: Stop the first time you reach the end word

The first time the search reaches the end word, its recorded distance is the answer, because every shorter path would already have been explored. If the queue empties first, no sequence exists and the answer is 0. Check the end word against the dictionary before starting: if it is absent, return 0 at once, as in the second example of the problem statement.

Input: the filled queue and the distance map. Output: one number. The search enqueues each word at most once. With N words of length L, building the N·L patterns costs O(N·L²) time and space, because each pattern string takes O(L) to build and hash. Scanning a bucket costs time proportional to its size, so the scan work is bounded by the sum of the squared bucket sizes, which is small for ordinary dictionaries and grows when a few buckets hold very many words.

1 · Words as nodes2 · Wildcard buckets3 · Queue by levels4 · Stop at the endReplay

Step-by-step description

1. Each word is a node.
2. Buckets such as h*t and *ot link one-letter neighbors.
3. The oldest word is expanded first, giving levels 1 to 5.
4. The first hit of cog, at level 5, is the answer.

• Each word is a node and a one-letter change is an edge.
• Wildcard buckets find neighbors by lookup.
• A queue explores level by level.
• The first time the end word is reached gives the answer.

from collections import deque, defaultdict

def ladder_length(begin, end, words):
    word_set = set(words)
    if end not in word_set:
        return 0
    buckets = defaultdict(list)          # pattern -> words that match it
    for w in word_set | {begin}:
        for i in range(len(w)):
            buckets[w[:i] + "*" + w[i + 1:]].append(w)
    dist = {begin: 1}                    # doubles as the visited set
    queue = deque([begin])
    while queue:
        w = queue.popleft()
        if w == end:
            return dist[w]
        for i in range(len(w)):
            for nxt in buckets[w[:i] + "*" + w[i + 1:]]:
                if nxt not in dist:      # mark when enqueued
                    dist[nxt] = dist[w] + 1
                    queue.append(nxt)
    return 0

The code follows the four steps in order. The dictionary dist serves as both the distance record and the seen set, so marking happens at enqueue time.

Worked example

Take the example from the problem statement: begin word hit, end word cog, word list hot, dot, dog, lot, log, cog. Running the code gives 5 words, which is 4 edges.¹ The levels explain why: hit is at distance 1, hot at 2, dot and lot at 3, dog and log at 4, and cog at 5.¹ If cog is removed from the list, the answer is 0.¹

The index for this toy list holds 14 distinct patterns, against an upper bound of 21 (seven words, three positions each).¹ Only 5 of the 14 patterns hold two or more words, and those are the only ones that create edges.¹

A lock is the same pattern with a different graph. Four wheels with ten digits each give 10,000 states, and one move turns one wheel up or down, so each state has 8 neighbors.¹ Blocked combinations are simply nodes you never enter. From 0000 to 2222, the distance is 8 moves. A one-sided search discovers 3,467 states before it stops, while a two-sided search that grows from both ends and always expands the smaller side discovers 457.¹

Text description of the diagram

• A search from one end discovers 3,467 lock states for a distance of 8.
• A search from both ends discovers 457 states for the same distance.

Trade-offs and edge cases

BFS answers "fewest steps", not "lowest cost". It counts edges, so it is correct only when every edge counts the same. If edges carry costs, use a different algorithm: Dijkstra's algorithm for non-negative costs, Bellman-Ford when some costs are negative and no negative cycle is reachable from the start, and 0-1 BFS when every cost is 0 or 1. The cp-algorithms site has a page on each. A broken teleporter that costs one extra day is a cost of 2 on that edge, so plain BFS is wrong there. When the only costs are 1 and 2, splitting each cost-2 edge with one dummy node makes plain BFS correct again.

Text description of the diagram

• BFS is correct only when every edge counts the same.
• Dijkstra suits varied costs that are not negative.
• Bellman-Ford when some costs are negative.

Search from both ends when you know the goal and the branching is large. Two searches that each go half the distance discover far fewer states, as the lock example shows, but the code is more complex and each round must expand the smaller frontier. Reported solutions to a connection-distance question use this idea; that is a candidate report, not a published rule.

Other edge cases: the begin word may be missing from the list; the end word must be in it; duplicates are excluded by the statement but not in other problems; and a graph with large buckets can have many edges, since the running time grows with edges as well as nodes. Heap-based problems such as K closest points to origin use a heap to order items, the same structure Dijkstra uses for its queue.

How to answer it in an interview

The spoken structure: name the graph, name the neighbor trick, name the queue rule, state the count, then say when BFS fails.

Common mistakes

• "BFS finds the shortest path in any graph." (wrong) It finds the fewest edges, which is the cheapest path only when all edges cost the same. (right) "BFS because every move costs one; with varied costs I would use Dijkstra."
• "The answer is the number of edges." (wrong) Word Ladder counts words. (right) "The path hit, hot, dot, dog, cog has four edges and five words, so I return five."
• "I mark words visited when I take them off the queue." (wrong) Duplicates pile up. (right) "I mark a word when I enqueue it."
• "I use a Python list as the queue." (wrong) Removing the first item shifts the rest. (right) "I use a deque for constant-time removal from the left." More on this in Python interview questions.
• "Bidirectional search is always faster." (wrong) It helps with a known goal and large branching, and costs more code. (right) "I would start with one-sided BFS and add the second side if the frontier is too big."

Follow-up questions

What if there are many calls on the same input?

Build the bucket index once and reuse it across calls, since it depends only on the dictionary. If many queries share a begin word, one BFS from it gives the distance to every reachable word, so later queries are lookups. For many different pairs, you can also store the full neighbor lists, trading memory for speed.

What if insertion or deletion can also be done on the words?

Neighbors now include words at edit distance one: a word of length 3 over 26 letters has up to 182 candidate edits, 75 substitutions, 3 deletions and 104 insertions.¹ Keep the wildcard buckets for substitutions. Also file each word under every version of itself with one letter removed, so insertions and deletions are found by lookup instead of by generating every candidate.

How do you find the shortest distance between two points in three dimensions with obstacles?

Without obstacles, the shortest distance is a straight line: the square root of the sum of the squared differences along each axis. With obstacles, make each unblocked grid cell a node joined to its six face neighbors and run BFS, which gives the fewest grid moves, not the true straight-line distance. A heuristic search such as A-star can explore less, but name BFS first; candidates report that such questions grow from plain distance to three dimensions and then to obstacles.

How do you handle teleporters that cost a day of repair?

Every teleporter jump costs one, and a broken one costs one more because of the repair day, so edge costs differ and plain BFS on the original graph is wrong. With costs of only 1 or 2, the cheaper fix is to split each cost-2 edge with one dummy node and run plain BFS. Dijkstra handles any non-negative costs, and 0-1 BFS applies if costs are only 0 or 1. If a repaired teleporter stays fixed for later use, the repair becomes part of the state, so a state is the node plus the set of repaired teleporters.

Why is bidirectional BFS used for connection paths?

On a social-style graph each person has many neighbors, so a one-sided search grows fast. Two searches that meet in the middle each cover half the distance, and the lock example shows 457 states discovered against 3,467.¹ Keep a parent record on both sides so the path can be printed.

Does Word Ladder return edges or words?

It returns words, so the edge count plus one. Always read the statement for this. Open the Lock, for example, returns the number of moves.

Sources

1. Word Ladder (problem 127) — LeetCode (statement undated; read 2026-10-26), 26 Oct 2026
2. Breadth First Search — cp-algorithms (undated; read 2026-10-26), 26 Oct 2026
3. Algorithms, 4th edition, section 4.1 Undirected Graphs — Sedgewick and Wayne, Princeton (undated; listed 2026-10-26), 26 Oct 2026
4. collections: deque — Python documentation (listed 2026-10-26), 26 Oct 2026