HardHash TableStringBreadth-First SearchUpdated Sep 2026

127. Word Ladder

Asked at Amazon, Apple

Difficulty

Hard

Time

O(n * L * 26)

Space

O(n * L)

Pattern

Hash Table

Companies

2

Problem

You are given two words, beginWord and endWord, and a list of allowed words called wordList. You want to walk from beginWord to endWord in steps.

Each step changes exactly one letter. Every word you land on (except the starting word) must appear in wordList. The starting word does not need to be in the list. All words have the same length.

Return the number of words in the shortest such sequence, counting both the start and the end word. If no sequence exists, return 0.

One letter per step

pathhithotdotdogcog01234hit → hot → dot → dog → cog, 5 words total
Each hop changes exactly one letter, and every word you land on must be in the list.

Constraints

  • ●1 <= beginWord.length <= 10
  • ●endWord.length == beginWord.length
  • ●1 <= wordList.length <= 5000
  • ●wordList[i].length == beginWord.length
  • ●beginWord, endWord, and wordList[i] consist of lowercase English letters
  • ●beginWord != endWord
  • ●All the words in wordList are unique

Examples

Example 1
InputbeginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output5
WhyThe path hit → hot → dot → dog → cog uses 5 words. Each arrow changes one letter, and every middle word is in the list. No shorter path exists.
Example 2
InputbeginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output0
WhyThe word "cog" is not in the list, so you can never land on it. No sequence exists.

Asked At

2 companies
CompanyDifficulty
AmazonHardView all Amazon questions →
AppleHardView all Apple questions →

How to Think About It

1

Think of each word as a node. Two words are connected if they differ by exactly one letter. The shortest transformation is the shortest path in this unweighted graph. BFS finds shortest paths in unweighted graphs.

2

Brute force: for each word in the list, check if it differs by one letter from the current word. That's O(n * L) per level where n = word list size and L = word length. Total: O(n * L * n) = O(n^2 * L). Too slow.

3

Optimization: preprocess words into wildcard patterns. For "hot", the patterns are "ot", "ht", "ho*". All words matching the same pattern are one letter apart. This reduces neighbor lookup from O(n) to O(L * 26) = O(26L). Total: O(n * L). Much better.

4

Edge cases: endWord not in wordList (return 0), no valid path (return 0), beginWord equals endWord (return 1 if endWord is in wordList, else 0).

Optimal Approach

Step 1: Put all words in a hash set for O(1) lookup.
Step 2: Preprocess words into wildcard patterns. For each word, create L patterns (one per position with "_" replacing that character). Map pattern -> list of words.
Step 3: BFS from beginWord. For each word, generate its L patterns. For each pattern, check all words matching that pattern. If a word is unvisited, add to BFS queue.
Step 4: When you reach endWord, return the number of levels + 1.
Step 5: If BFS exhausts without finding endWord, return 0.

Alternatively, without preprocessing: for each word, try all 26 letters at each position. If the resulting word is in the set, it's a neighbor. Same time complexity.

Time: O(n * L * 26) where n = word list size, L = word length. Space: O(n * L) for the pattern map.

BFS over the word graph

level 1hit0Start: queue holds the begin word at distance 1level 2hot0From hit, only hot differs by one letter and is in thelistlevel 3dotlot01hot reaches dot and lot, both one letter awaylevel 4doglog01dot → dog and lot → log; next step both reach cog
BFS explores words level by level, so the first time we reach endWord we have the shortest path.
ComplexityTime O(n * L * 26)Space O(n * L)n is the number of words and L is the word length; the cost comes from trying 26 letters at each of the L positions for every word visited.

What Trips People Up in Real Interviews

1

Building a full graph by comparing every word pair. That's O(n^2 * L) and too slow. Use wildcard patterns or letter-by-letter replacement to find neighbors in O(n * L).

2

Forgetting to mark visited words. Without a visited set, BFS loops forever on cycles (hit -> hot -> hit -> ...). Always mark words when you enqueue them, not when you dequeue.

3

Returning the level count instead of the transformation sequence length. The answer is the number of words in the sequence (including beginWord and endWord), not the number of edges.

4

Not checking if endWord exists in wordList upfront. If it doesn't, no valid transformation exists. Return 0 immediately.

5

Using DFS instead of BFS. DFS doesn't guarantee the shortest path. BFS explores level by level, so the first time you reach endWord, it's guaranteed to be the shortest transformation.

Solution Code

O(n * L * 26) time
from collections import deque

def ladderLength(beginWord, endWord, wordList):
    wordSet = set(wordList)
    if endWord not in wordSet:
        return 0
    queue = deque([(beginWord, 1)])
    visited = {beginWord}
    while queue:
        word, steps = queue.popleft()
        for i in range(len(word)):
            for ch in 'abcdefghijklmnopqrstuvwxyz':
                newWord = word[:i] + ch + word[i+1:]
                if newWord == endWord:
                    return steps + 1
                if newWord in wordSet and newWord not in visited:
                    visited.add(newWord)
                    queue.append((newWord, steps + 1))
    return 0

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Word Ladder problem?

Given two words (beginWord and endWord) and a word list, find the shortest transformation sequence from beginWord to endWord, changing one letter at a time. Each intermediate word must be in the word list. This is a classic BFS shortest-path problem on an implicit word graph.

How do you solve Word Ladder?

The optimal approach runs in O(n * L * 26) time and O(n * L) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Word Ladder?

Word Ladder is asked at Amazon, Apple. It is a hard difficulty problem.

What are common mistakes on Word Ladder?
  • Building a full graph by comparing every word pair. That's `O(n^2 * L)` and too slow. Use wildcard patterns or letter-by-letter replacement to find neighbors in `O(n * L)`.
  • Forgetting to mark visited words. Without a visited set, BFS loops forever on cycles (hit -> hot -> hit -> ...). Always mark words when you enqueue them, not when you dequeue.
  • Returning the level count instead of the transformation sequence length. The answer is the number of words in the sequence (including beginWord and endWord), not the number of edges.
  • Not checking if endWord exists in wordList upfront. If it doesn't, no valid transformation exists. Return 0 immediately.
  • Using `DFS` instead of `BFS`. DFS doesn't guarantee the shortest path. `BFS` explores level by level, so the first time you reach endWord, it's guaranteed to be the shortest transformation.