30% off Lifetime Premium Access expires December 2nd!

30% off Lifetime Premium Access expires Dec 2nd!

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Get Premium

Leetcode 127. Word Ladder

Find the length of the shortest transformation sequence from beginWord to endWord where each step changes exactly one letter and every intermediate word must be in wordList — treat words as nodes in an implicit graph with edges between one-letter-different words. Return the number of words in that shortest path (or 0 if endWord isn't reachable).

Asked at:

Amazon

SoFi

Uber

DESCRIPTION

You are given two words, beginWord and endWord, along with a dictionary of words called wordList.
A transformation sequence is a sequence of words that starts with beginWord and ends with endWord, where:

Each consecutive pair of words differs by exactly one letter.
Every intermediate word in the sequence must exist in wordList.
(Note that beginWord itself does not need to be in wordList.)
The final word of the sequence is endWord.

Your task is to determine the length of the shortest transformation sequence from beginWord to endWord.
If no such sequence exists, return 0.

Input:


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

Output:

Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> "cog".

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 strings in wordList are unique

Note: beginWord does not need to be in wordList

endWord must be in wordList for a valid transformation to exist

Each transformation changes exactly one letter

Understanding the Problem

This problem is asking us to find the shortest path between two nodes in an unweighted graph. Each word represents a node, and there's an edge between two words if they differ by exactly one character.

The transformation sequence represents a path through this graph, where we can only step on nodes (words) that exist in our wordList. We need to find the shortest such path from beginWord to endWord.

The constraint that each consecutive pair differs by exactly one letter means we're working with a very specific graph structure - each word can connect to at most 26 * word_length other words (changing each position to each possible letter).

Brute Force Approach

The most straightforward approach would be to use DFS with backtracking to explore all possible transformation paths from beginWord to endWord. We would recursively try changing each character of the current word to every possible letter (a-z), check if the resulting word exists in wordList, and continue the search.

This approach would explore every possible path in the transformation graph, potentially visiting the same word multiple times through different paths. We'd need to track visited words in each path to avoid cycles, but we couldn't globally mark words as visited since they might be part of different valid paths.

The major inefficiency comes from exploring longer paths even after we've found shorter ones, and from the exponential nature of trying all possible character combinations at each step without any optimization for finding the shortest path.


def ladderLength(beginWord, endWord, wordList):
    if endWord not in wordList:
        return 0
    
    def can_transform(word1, word2):
        if len(word1) != len(word2):
            return False
        diff = 0
        for i in range(len(word1)):
            if word1[i] != word2[i]:
                diff += 1
                if diff > 1:
                    return False
        return diff == 1
    
    def dfs(current, target, words, visited, depth):
        if current == target:
            return depth
        
        min_length = float('inf')
        for i in range(len(words)):
            if not visited[i] and can_transform(current, words[i]):
                visited[i] = True
                result = dfs(words[i], target, words, visited, depth + 1)
                if result != 0:
                    min_length = min(min_length, result)
                visited[i] = False
        
        return 0 if min_length == float('inf') else min_length
    
    visited = [False] * len(wordList)
    return dfs(beginWord, endWord, wordList, visited, 1)

0 / 190

Test Your Knowledge

Complexity Analysis

Time Complexity: O(26^(M*L)) where M is word length and L is the maximum path length Due to checking all possible combinations

Space Complexity: O(M * L) for recursion stack and path tracking Additional space for tracking

Building Intuition

The breakthrough insight is recognizing this as a shortest path problem in an unweighted graph, where BFS guarantees optimality. The graph doesn't need to be explicitly built - we can generate valid neighbors dynamically by trying all single-character changes and checking against our word set.

After seeing the brute force limitations of exploring all paths, BFS emerges as the perfect algorithm because it guarantees finding the shortest path in unweighted graphs.

BFS explores nodes level by level - all nodes at distance 1, then distance 2, then distance 3, and so on. This means the first time we encounter our target (endWord), we've found it via the shortest possible path.

The graph structure is implicit but well-defined: we can generate neighbors on-the-fly by trying all single-character modifications. Using a set for wordList gives us O(1) neighbor validation, making the graph traversal efficient.

BFS also naturally handles the constraint that intermediate words must exist in wordList - we simply don't add invalid words to our queue.

Common Mistakes

Using DFS instead of BFS and missing the shortest path guarantee

Not removing visited words from the set, leading to cycles and incorrect results

Trying to build the entire graph upfront instead of generating neighbors dynamically

Forgetting to check if endWord exists in wordList before starting the search

Not handling the case where beginWord equals endWord

Optimal Solution

Now that we understand why BFS is perfect for finding shortest paths, here's how we implement it effectively. We treat this as an unweighted graph problem where each word is a node, and edges exist between words that differ by exactly one character.

We start BFS from beginWord, exploring all words reachable in one transformation, then all words reachable in two transformations, and so on. The key optimization is using a set for wordList to achieve O(1) lookup time when checking if a transformed word exists.

For each word in our current BFS level, we systematically try changing each character position to every letter a-z. If the resulting word exists in our word set and hasn't been visited, we add it to the next BFS level. We mark words as visited immediately to prevent revisiting them in longer paths.

The moment we encounter endWord, we can return the current path length since BFS guarantees this is the shortest possible transformation sequence.


from collections import deque

def ladderLength(beginWord, endWord, wordList):
    if endWord not in wordList:
        return 0
    
    word_set = set(wordList)
    queue = deque([(beginWord, 1)])
    visited = set([beginWord])
    
    while queue:
        word, length = queue.popleft()
        
        if word == endWord:
            return length
        
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                if c == word[i]:
                    continue
                
                new_word = word[:i] + c + word[i+1:]
                
                if new_word in word_set and new_word not in visited:
                    visited.add(new_word)
                    queue.append((new_word, length + 1))
    
    return 0

0 / 21

Test Your Knowledge

Complexity Analysis

Time Complexity: O(M * N * 26) where M is the number of words we visit and N is the word length, since for each visited word we try 26 character substitutions Single pass through the data

Space Complexity: O(N) for the wordList set, visited set, and BFS queue storage Space for the data structure

What We've Learned

BFS for shortest path: When a problem asks for the shortest/minimum number of steps between two states, think BFS - it explores all possibilities level by level, guaranteeing the first time you reach the target is the shortest path.
Graph modeling technique: Transform word transformation into a graph problem where each word is a node and edges connect words differing by exactly one character - this converts a string manipulation problem into a well-understood graph traversal.
Set-based neighbor generation: Instead of checking every word in the dictionary, generate all possible one-character variations of the current word and check if they exist in a HashSet - this reduces time complexity from O(N*M) to O(M²) where M is word length.
Early termination optimization: Always check if the endWord exists in wordList before starting BFS - this simple validation prevents unnecessary computation and handles a common edge case that would otherwise require full traversal to detect.
Bidirectional BFS pattern: For large search spaces, implement bidirectional BFS starting from both ends simultaneously - this reduces time complexity from O(b^d) to O(b^(d/2)) where b is branching factor and d is depth.
State space exploration: This pattern applies to any problem involving minimum steps between states - DNA mutation, puzzle solving, or configuration changes - where each state has a limited set of valid transitions to neighboring states.

Test Your Understanding

Why is graph the right data structure for this problem?

graph provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Late July, 2025

SoFi

Manager

Late April, 2025

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 127. Word Ladder

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact