What is the brute force approach and complexity for Word Ladder?

Compare every pair of words to build the graph, then run BFS from beginWord with time complexity O(N² · L) and space complexity O(N²).

What is the optimal approach and complexity for Word Ladder?

BFS from beginWord; from each word, try every one-letter change and look it up in a hash set with optimal time complexity O(N · L · 26) and space complexity O(N · L).

How do you identify the pattern for Word Ladder?

Look for key signals in the prompt: "change one letter at a time" indicates Each one-letter change is an edge of length 1, so the question is a shortest-path count. BFS by levels gives it.; "number of words in the sequence" indicates Count words, not changes. beginWord is the first word, so the count starts at 1.; "from wordList" indicates Only words in the set can be visited. Erasing a word when it is queued also makes sure it is queued once..

Word Ladder

Hard·LeetCode #127 Pro OnlyPattern Transfer

LeetCode

Problem Statement

You are given two words, beginWord and endWord, and a list of words, wordList. A step changes exactly one letter of a word.

A word ladder is a sequence of words that starts at beginWord and ends at endWord. Each word differs from the word before it by one letter, and every word after beginWord must be in wordList. The beginWord does not have to be in the list.

Return the number of words in the shortest such sequence, counting beginWord and endWord. Counting words is not the same as counting steps: a sequence of 5 words has 4 steps. If no sequence exists, return 0.

Input

beginWord and endWord, two words of the same length. wordList, the words that may be used.

Output

The number of words in the shortest sequence, or 0 if there is none.

Example 1

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

Output: 5

One shortest sequence is hit → hot → dot → dog → cog. It has 5 words, so the answer is 5 (not the 4 steps between them).

Example 2

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

Output: 0

cog is not in the list, so no sequence can end on it.

Example 3

Input: beginWord = "aa", endWord = "bb", wordList = ["ab","bb"]

Output: 3

aa → ab → bb. Three words, two steps.

Constraints

• All words have the same length, from 1 to 10 letters.
• The list has between 1 and 5000 words, and every word in it is unique.
• All words use only the lowercase letters a to z.
• beginWord and endWord are different words.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“change one letter at a time”

→ Each one-letter change is an edge of length 1, so the question is a shortest-path count. BFS by levels gives it.

“number of words in the sequence”

→ Count words, not changes. beginWord is the first word, so the count starts at 1.

“from wordList”

→ Only words in the set can be visited. Erasing a word when it is queued also makes sure it is queued once.

Approach Complexity Ladder

Brute Force — build the whole graph by comparing every pair, then BFSO(N² · L)O(N²)

Compare every pair of words to build the graph, then run BFS from beginWord

Optimal — BFS that tries every one-letter changeO(N · L · 26)O(N · L)

BFS from beginWord; from each word, try every one-letter change and look it up in a hash set

Brute Force Intuition

First build the graph. Check every pair of words, and connect a pair when they differ in exactly one letter. Then run BFS from beginWord, counting words. The count when endWord is reached is the answer.

Recognition rule for this sub-pattern:

Nodes are states (lock codes, words, board squares). Generate neighbours on the fly.

Remember this · Graph BFS / DFS

Trigger

Grid of cells, islands, regions, "minimum steps", transformations between states, connected components.

Think

What is a node, what is an edge, and do I need the shortest path or just reachability?

Key question

How do I mark visited so I never process a node twice?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Graph BFS / DFS translate into production architectures and low-level memory mechanics.

LLD Real-World Story

Food Delivery System (Zomato / DoorDash)

Geospatial indexing and shortest dispatch routing for delivery partners.

Explore Track

C++ Internals

Virtual Method Table (vtable) & Dynamic Dispatch

Polymorphic graph nodes and state machine execution overhead.

Explore Track

The Maze