Skip to main content
Talentd

Word Ladder - Solution & Explanation

HardHash TableStringBreadth-First Search23 min readAsked at: Amazon, Microsoft, Apple +38
Practice this problem

Problem Statement

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

  • Every adjacent pair of words differs by a single letter.
  • Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
  • sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

 

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

Example 2:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.

 

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.

Approach Overview

Problem Overview: Given a beginWord, endWord, and a dictionary of valid words, compute the length of the shortest transformation sequence where only one character can change at a time and every intermediate word must exist in the dictionary.

Approach 1: Graph Construction + Breadth‑First Search (O(N^2 * L) time, O(N^2) space)

Treat every word as a node in a graph. Two nodes connect if the words differ by exactly one character. Building this graph requires comparing every pair of words and checking if they differ by one position, which costs O(N^2 * L) where N is the number of words and L is the word length. After constructing the adjacency list, run Breadth‑First Search from beginWord to find the shortest path to endWord. BFS guarantees the minimum number of transformations because it explores level by level. This approach is conceptually simple but wastes time building a dense graph that may never be fully explored.

Approach 2: BFS with Word Transformations (O(N * L * 26) time, O(N) space)

The optimized solution avoids explicitly building the entire graph. Store the dictionary in a hash table for O(1) lookups. Starting from beginWord, perform Breadth‑First Search. For each word popped from the queue, iterate through every character position and try replacing it with letters 'a' to 'z'. Each generated candidate word represents a possible transformation. If the word exists in the dictionary and hasn't been visited, push it into the queue and remove it from the set to prevent revisits. Each word can generate up to L * 26 neighbors, and each valid word is processed once, giving overall time complexity O(N * L * 26) with O(N) memory for the queue and visited structure. This method implicitly explores the graph without building it.

Recommended for interviews: The BFS transformation approach is the expected solution. It shows you recognize that the problem is a shortest‑path search in an unweighted graph and that you can generate neighbors dynamically using string manipulation. A brute-force graph build demonstrates understanding of the problem structure, but interviewers typically look for the optimized BFS that combines hashing and on‑the‑fly neighbor generation.

Approach 1: Breadth First Search with Word Transformations

This approach leverages Breadth First Search (BFS), where each word is a node in the graph, and an edge exists between two nodes if they differ by exactly one letter. The goal is to find the shortest path from beginWord to endWord.

Start BFS from the beginWord, exploring transformations by changing each letter and checking if the new word exists in the set of available words. Polished implementation should consider preprocessing the word list for efficient lookup.

This C solution uses BFS to navigate from the beginWord to the endWord. It maintains a queue for exploration, marking words as visited to prevent revisiting them. The function oneLetterDifference checks if two words differ by exactly one letter, crucial for establishing edges in the BFS traversal.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N * m^2), where N is the number of words in the list and m is the length of each word. Each word pair is compared in the worst case.
Space Complexity: O(N), where N is the number of nodes (words) we store in the queue.

Try this approach in the editor →

Approach 2: BFS

BFS minimum step model. This problem can be solved with naive BFS, or it can be optimized with bidirectional BFS to reduce the search space and improve efficiency.

Bidirectional BFS is a common optimization method for BFS, with the main implementation ideas as follows:

  1. Create two queues, q1 and q2, for "start -> end" and "end -> start" search directions, respectively.
  2. Create two hash maps, m1 and m2, to record the visited nodes and their corresponding expansion times (steps).
  3. During each search, prioritize the queue with fewer elements for search expansion. If a node visited from the other direction is found during the expansion, it means the shortest path has been found.
  4. If one of the queues is empty, it means that the search in the current direction cannot continue, indicating that the start and end points are not connected, and there is no need to continue the search.
while q1 and q2:
    if len(q1) <= len(q2):
        # Prioritize the queue with fewer elements for expansion
        extend(m1, m2, q1)
    else:
        extend(m2, m1, q2)


def extend(m1, m2, q):
    # New round of expansion
    for _ in range(len(q)):
        p = q.popleft()
        step = m1[p]
        for t in next(p):
            if t in m1:
                # Already visited before
                continue
            if t in m2:
                # The other direction has been searched, indicating that a shortest path has been found
                return step + 1 + m2[t]
            q.append(t)
            m1[t] = step + 1

Code

PythonJavaC++GoC#TypeScript

Python

Java

C++

Go

C#

TypeScript

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Breadth First Search with Word Transformations

Time Complexity: O(N * m^2), where N is the number of words in the list and m is the length of each word. Each word pair is compared in the worst case.
Space Complexity: O(N), where N is the number of nodes (words) we store in the queue.

BFS—
Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Explicit Graph Build + BFSO(N^2 * L)O(N^2)Useful for understanding the graph structure or when the dataset is very small
BFS with On‑the‑Fly Word TransformationsO(N * L * 26)O(N)General case and interview‑optimal solution for large dictionaries

Video Solution

G-29. Word Ladder - I | Shortest Paths • take U forward • 432,262 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Word Ladder easy or hard?
Word Ladder is classified as Hard on LeetCode because the key insight is recognizing the implicit graph and generating neighbors efficiently. Implementing BFS alone is straightforward, but optimizing neighbor generation and avoiding repeated work makes it challenging.
Word Ladder Python/Java solution
Implement BFS starting from beginWord. Store the word list in a hash set, generate neighbors by replacing each character with 'a'–'z', and push valid transformations into the queue. Track levels to count the transformation length. The same logic works in Python, Java, C++, C#, and JavaScript.
How to solve Word Ladder in O(n)?
A strict O(n) solution is not possible because each word requires generating multiple character transformations. The practical optimal approach is O(N * L * 26) using BFS and a hash set. Each valid word is processed once while generating at most L * 26 candidate transformations.
What is the best approach for Word Ladder?
Breadth-First Search with on-the-fly word transformations is the best approach. Store the dictionary in a hash set and generate neighbors by changing each character to 'a'–'z'. BFS guarantees the shortest transformation path. The complexity is O(N * L * 26) time and O(N) space.
Is Word Ladder asked at Google/Amazon/Meta?
Word Ladder frequently appears in interviews at companies like Amazon, Google, and Meta because it tests graph modeling and BFS traversal. Candidates must recognize that words form nodes in an implicit graph and use BFS to compute the shortest path.
What data structure is used in Word Ladder?
The core data structures are a queue for Breadth-First Search and a hash set for fast dictionary lookups and visited tracking. Strings are manipulated to generate neighbors by changing one character at a time.
What is the time complexity of Word Ladder?
The optimized BFS solution runs in O(N * L * 26) time, where N is the number of words and L is the word length. For each word processed, every position can be replaced with 26 possible characters to generate candidate neighbors. Space complexity is O(N) for the queue and visited set.

Ready to solve this problem?

Practice Word Ladder with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Genetic Mutation

Next

Word Ladder II