127. Word Ladder - Explanation

Problem Link

Description

You are given two words, beginWord and endWord, and also a list of words wordList. All of the given words are of the same length, consisting of lowercase English letters, and are all distinct.

Your goal is to transform beginWord into endWord by following the rules:

  • You may transform beginWord to any word within wordList, provided that at exactly one position the words have a different character, and the rest of the positions have the same characters.
  • You may repeat the previous step with the new word that you obtain, and you may do this as many times as needed.

Return the minimum number of words within the transformation sequence needed to obtain the endWord, or 0 if no such sequence exists.

Example 1:

Input: beginWord = "cat", endWord = "sag", wordList = ["bat","bag","sag","dag","dot"]

Output: 4

Explanation: The transformation sequence is "cat" -> "bat" -> "bag" -> "sag".

Example 2:

Input: beginWord = "cat", endWord = "sag", wordList = ["bat","bag","sat","dag","dot"]

Output: 0

Explanation: There is no possible transformation sequence from "cat" to "sag" since the word "sag" is not in the wordList.

Constraints:

  • 1 <= beginWord.length <= 10
  • 1 <= wordList.length <= 100


Topics

Hash Table String Breadth-First Search

Recommended Time & Space Complexity

You should aim for a solution with O((m ^ 2) * n) time and O((m ^ 2) * n) space, where n is the number of words and m is the length of the word.


Hint 1

Consider the given problem in terms of a graph, treating strings as nodes. Think of a way to build edges where two strings have an edge if they differ by a single character. A naive approach would be to consider each pair of strings and check whether an edge can be formed. Can you think of an efficient way? For example, consider a string hot and think about the strings that can be formed from it by changing a single letter.


Hint 2

To efficiently build edges, consider transforming each word into intermediate states by replacing one character with a wildcard, like *. For example, the word hot can be transformed into *ot, h*t, and ho*. These intermediate states act as "parents" that connect words differing by one character. For instance, *ot can connect to words like cot. For each word in the list, generate all possible patterns by replacing each character with * and store the word as a child of these patterns. We can run a BFS starting from the beginWord, visiting other words while avoiding revisiting by using a hash set.


Hint 3

When visiting a node during BFS, if the word matches the endWord, we immediately return true. Otherwise, we generate the pattern words that can be formed from the current word and attempt to visit the words connected to these pattern words. We add only unvisited words to the queue. If we exhaust all possibilities without finding the endWord, we return false.


Company Tags

Please upgrade to NeetCode Pro to view company tags.



Prerequisites

Before attempting this problem, you should be comfortable with:

  • Breadth-First Search (BFS) - Finding the shortest path in an unweighted graph using level-order traversal
  • Graph Representation - Building adjacency lists and understanding implicit graphs where nodes are words
  • Hash Maps and Hash Sets - For O(1) word lookups and tracking visited nodes
  • String Manipulation - Generating neighbor words by changing one character at a time
  • Queue Data Structure - Essential for implementing BFS traversal

1. Breadth First Search - I

Intuition

This problem can be modeled as finding the shortest path in an unweighted graph where each word is a node and edges connect words that differ by exactly one character. We precompute the adjacency list by comparing all pairs of words. BFS naturally finds the shortest path because it explores all nodes at distance k before any node at distance k+1.

Algorithm

  1. Create a mapping from each word to its index in the word list.
  2. Build an adjacency list by comparing all word pairs; connect words that differ by exactly one character.
  3. Find all words that differ by one character from beginWord and add them to the BFS queue.
  4. Process the queue level by level, incrementing the distance counter at each level.
  5. When endWord is found, return the current distance. If the queue empties, return 0.
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if (endWord not in wordList) or (beginWord == endWord):
            return 0

        n, m = len(wordList), len(wordList[0])
        adj = [[] for _ in range(n)]
        mp = {}
        for i in range(n):
            mp[wordList[i]] = i

        for i in range(n):
            for j in range(i + 1, n):
                cnt = 0
                for k in range(m):
                    if wordList[i][k] != wordList[j][k]:
                        cnt += 1
                if cnt == 1:
                    adj[i].append(j)
                    adj[j].append(i)

        q, res = deque(), 1
        visit = set()
        for i in range(m):
            for c in range(97, 123):
                if chr(c) == beginWord[i]:
                    continue
                word = beginWord[:i] + chr(c) + beginWord[i + 1:]
                if word in mp and mp[word] not in visit:
                    q.append(mp[word])
                    visit.add(mp[word])

        while q:
            res += 1
            for i in range(len(q)):
                node = q.popleft()
                if wordList[node] == endWord:
                    return res
                for nei in adj[node]:
                    if nei not in visit:
                        visit.add(nei)
                        q.append(nei)

        return 0

Time & Space Complexity

  • Time complexity: O(n2∗m)O(n ^ 2 * m)
  • Space complexity: O(n2)O(n ^ 2)

Where nn is the number of words and mm is the length of the word.

2. Breadth First Search - II

Intuition

Instead of precomputing the entire adjacency graph, we can generate neighbors on the fly. For each word, we try replacing each character with all 26 letters. If the resulting word exists in our word set, it is a valid neighbor. This approach trades precomputation time for potentially more neighbor generation during BFS.

Algorithm

  1. Convert the word list to a set for O(1) lookups.
  2. Start BFS from beginWord with distance counter set to 0.
  3. For each word in the current level, generate all possible words by changing one character at a time.
  4. If a generated word is in the word set, add it to the queue and remove it from the set to mark as visited.
  5. Return the distance when endWord is found, or 0 if the queue empties.
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if (endWord not in wordList) or (beginWord == endWord):
            return 0
        words, res = set(wordList), 0
        q = deque([beginWord])
        while q:
            res += 1
            for _ in range(len(q)):
                node = q.popleft()
                if node == endWord:
                    return res
                for i in range(len(node)):
                    for c in range(97, 123):
                        if chr(c) == node[i]:
                            continue
                        nei = node[:i] + chr(c) + node[i + 1:]
                        if nei in words:
                            q.append(nei)
                            words.remove(nei)
        return 0

Time & Space Complexity

  • Time complexity: O(m2∗n)O(m ^ 2 * n)
  • Space complexity: O(m2∗n)O(m ^ 2 * n)

Where nn is the number of words and mm is the length of the word.

3. Breadth First Search - III

Intuition

We can use wildcard patterns to efficiently group words that are one character apart. For each word, create patterns by replacing each character with a wildcard. Words sharing the same pattern are neighbors. This precomputation allows O(1) neighbor lookup during BFS, as we only need to check the pattern buckets.

Algorithm

  1. For each word in the list (including beginWord), generate patterns by replacing each character with '*' and group words by these patterns.
  2. Start BFS from beginWord, maintaining a visited set.
  3. For the current word, generate its patterns and look up all words in corresponding pattern buckets.
  4. Add unvisited neighbors to the queue and mark them visited.
  5. Return the level count when endWord is reached, or 0 if unreachable.
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList:
            return 0

        nei = collections.defaultdict(list)
        wordList.append(beginWord)
        for word in wordList:
            for j in range(len(word)):
                pattern = word[:j] + "*" + word[j + 1 :]
                nei[pattern].append(word)

        visit = set([beginWord])
        q = deque([beginWord])
        res = 1
        while q:
            for i in range(len(q)):
                word = q.popleft()
                if word == endWord:
                    return res
                for j in range(len(word)):
                    pattern = word[:j] + "*" + word[j + 1 :]
                    for neiWord in nei[pattern]:
                        if neiWord not in visit:
                            visit.add(neiWord)
                            q.append(neiWord)
            res += 1
        return 0

Time & Space Complexity

  • Time complexity: O(m2∗n)O(m ^ 2 * n)
  • Space complexity: O(m2∗n)O(m ^ 2 * n)

Where nn is the number of words and mm is the length of the word.

4. Meet In The Middle (BFS)

Intuition

Standard BFS explores exponentially more nodes as distance increases. By running two BFS searches simultaneously from beginWord and endWord, we can meet in the middle, effectively halving the search depth and dramatically reducing the search space. At each step, we expand the smaller frontier to balance the workload.

Algorithm

  1. Initialize two queues: one from beginWord and one from endWord.
  2. Maintain two maps tracking the distance from each end for visited words.
  3. Always expand the smaller queue to minimize work.
  4. For each word, generate neighbors by changing one character at a time.
  5. If a neighbor is already visited by the other search, return the sum of both distances.
  6. Otherwise, if unvisited by the current search, add to queue and record distance.
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList or beginWord == endWord:
            return 0
        m = len(wordList[0])
        wordSet = set(wordList)
        qb, qe = deque([beginWord]), deque([endWord])
        fromBegin, fromEnd = {beginWord: 1}, {endWord: 1}

        while qb and qe:
            if len(qb) > len(qe):
                qb, qe = qe, qb
                fromBegin, fromEnd = fromEnd, fromBegin
            for _ in range(len(qb)):
                word = qb.popleft()
                steps = fromBegin[word]
                for i in range(m):
                    for c in range(97, 123):
                        if chr(c) == word[i]:
                            continue
                        nei = word[:i] + chr(c) + word[i + 1:]
                        if nei not in wordSet:
                            continue
                        if nei in fromEnd:
                            return steps + fromEnd[nei]
                        if nei not in fromBegin:
                            fromBegin[nei] = steps + 1
                            qb.append(nei)
        return 0

Time & Space Complexity

  • Time complexity: O(m2∗n)O(m ^ 2 * n)
  • Space complexity: O(m2∗n)O(m ^ 2 * n)

Where nn is the number of words and mm is the length of the word.

Common Pitfalls

Returning Distance Instead of Word Count

The problem asks for the number of words in the transformation sequence, not the number of transformations (edges). Off-by-one errors occur when returning the edge count instead of the node count.

# Wrong: returns number of transformations
res = 0  # starts at 0, counts edges
while q:
    res += 1
    # ...
    if word == endWord:
        return res  # off by one

# Correct: count includes beginWord
res = 1  # starts at 1, counts nodes

Forgetting to Check if endWord Exists in wordList

If the endWord is not in the word list, transformation is impossible. Skipping this check leads to unnecessary BFS traversal and potential incorrect results.

# Wrong: missing check
def ladderLength(beginWord, endWord, wordList):
    # starts BFS immediately...

# Correct: check first
if endWord not in wordList:
    return 0

Not Marking Words as Visited Before Adding to Queue

Adding a word to the queue without immediately marking it visited allows the same word to be added multiple times from different neighbors, causing duplicate processing and incorrect distance calculations.

# Wrong: mark visited when dequeuing
node = q.popleft()
visit.add(node)  # too late, duplicates already in queue

# Correct: mark visited when enqueuing
if nei in words and nei not in visit:
    visit.add(nei)  # mark immediately
    q.append(nei)

Comparing Characters at Same Position in Neighbor Generation

When generating neighbor words by changing one character, forgetting to skip the original character at each position generates the same word as a "neighbor."

# Wrong: includes original word as neighbor
for c in 'abcdefghijklmnopqrstuvwxyz':
    nei = word[:i] + c + word[i+1:]  # when c == word[i]

# Correct: skip the original character
for c in 'abcdefghijklmnopqrstuvwxyz':
    if c == word[i]:
        continue
    nei = word[:i] + c + word[i+1:]

Using DFS Instead of BFS for Shortest Path

DFS finds a path but not necessarily the shortest. BFS guarantees the shortest path in an unweighted graph by exploring all nodes at distance k before distance k+1.

# Wrong: DFS may find longer path first
def dfs(word, depth):
    if word == endWord:
        return depth
    for nei in getNeighbors(word):
        result = dfs(nei, depth + 1)
        if result:
            return result  # not necessarily shortest

# Correct: BFS guarantees shortest path
while q:
    word = q.popleft()
    if word == endWord:
        return distance[word]  # guaranteed shortest