Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Word Ladder

HARDProblemSolveExternal Links

Description

You are given two words, beginWord and endWord, along with a list of words called wordList. A transformation sequence from beginWord to endWord is a chain of words beginWord → s₁ → s₂ → ... → sₖ where:

  • Every consecutive pair of words in the chain differs by exactly one letter.
  • Every intermediate word sᵢ (for 1 ≤ i ≤ k) must exist in wordList. Note that beginWord does not need to be in wordList.
  • The last word sₖ must equal endWord.

Return the number of words in the shortest such transformation sequence. If no valid transformation sequence exists, return 0.

For example, transforming "hit" into "cog" through the chain "hit" → "hot" → "dot" → "dog" → "cog" gives a sequence of length 5 (count every word in the chain, including both beginWord and endWord).

Examples

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"

This chain has 5 words in total. At each step, only a single character changes:

  • "hit" → "hot" (change 'i' to 'o' at position 1)
  • "hot" → "dot" (change 'h' to 'd' at position 0)
  • "dot" → "dog" (change 't' to 'g' at position 2)
  • "dog" → "cog" (change 'd' to 'c' at position 0)

Another valid shortest path is "hit" → "hot" → "lot" → "log" → "cog" — also length 5.

Example 2

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

Output: 0

Explanation: The endWord "cog" is not present in the wordList. Since every intermediate word and the endWord must exist in the wordList, there is no valid transformation sequence. The answer is 0.

Example 3

Input: beginWord = "a", endWord = "c", wordList = ["a", "b", "c"]

Output: 2

Explanation: The beginWord "a" and endWord "c" differ by one character. Since "c" is in the wordList, the shortest transformation is just "a" → "c", which is 2 words long.

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

Editorial

Brute Force

Intuition

The most natural way to approach this problem is to think of it as exploring all possible transformation paths. Starting from beginWord, at each step we try every word in the dictionary that differs by exactly one letter. We recursively explore deeper and deeper, tracking the path length, until we either reach endWord or run out of options.

Imagine you are in a maze of rooms, where each room has a word written on the door. You can only move to an adjacent room if the word on its door differs from your current room's word by exactly one letter. You want to find the shortest path from the entrance (beginWord) to the exit (endWord).

The brute force idea is: try every door that's one-letter-different, walk through it, then from that new room try every one-letter-different door again, and so on. We use backtracking — if a path leads to a dead end, we retrace our steps and try a different door.

To avoid infinite loops (going back and forth between two rooms), we mark each word as visited along the current path and unmark it when backtracking.

Step-by-Step Explanation

Let's trace through with beginWord = "hit", endWord = "cog", wordList = ["hot", "dot", "dog", "lot", "log", "cog"]:

Step 1: Start at "hit". Mark "hit" as visited. Current path length = 1.

Step 2: Find all words in wordList differing from "hit" by one letter. Check each:

  • "hot": h-i-t vs h-o-t → differ at position 1 only → YES, neighbor
  • "dot": h-i-t vs d-o-t → differ at positions 0 and 1 → NO (2 differences)
  • "dog": 3 differences → NO
  • "lot": differ at positions 0 and 1 → NO
  • "log": 3 differences → NO
  • "cog": 3 differences → NO
    Only neighbor: "hot".

Step 3: Move to "hot". Mark visited. Path length = 2. Find neighbors of "hot":

  • "dot": h-o-t vs d-o-t → differ at position 0 → YES
  • "lot": h-o-t vs l-o-t → differ at position 0 → YES
  • "dog": differ at positions 0 and 2 → NO
  • "log": differ at positions 0 and 2 → NO
  • "cog": differ at positions 0 and 2 → NO
    Neighbors: "dot", "lot".

Step 4: Try "dot". Mark visited. Path length = 3. Find neighbors of "dot":

  • "hot": visited → skip
  • "dog": d-o-t vs d-o-g → differ at position 2 → YES
  • "lot": d-o-t vs l-o-t → differ at position 0 → YES
    Neighbors: "dog", "lot".

Step 5: Try "dog". Mark visited. Path length = 4. Find neighbors of "dog":

  • "dot": visited → skip
  • "cog": d-o-g vs c-o-g → differ at position 0 → YES
  • "log": d-o-g vs l-o-g → differ at position 0 → YES
    Neighbors: "cog", "log".

Step 6: Try "cog" — this equals endWord! Path length = 5. Record this as a candidate answer (minimum so far = 5).

Step 7: Backtrack and try "log" from step 5. Path length = 5 → "log" → neighbors include "cog" (path = 6, worse than 5). This branch can't improve.

Step 8: Continue backtracking through "lot" branch from step 4, etc. All other paths are length ≥ 5.

Result: The minimum path length found is 5.

Algorithm

  1. Place all words from wordList into a set for O(1) lookup
  2. If endWord is not in the set, return 0 immediately
  3. Define a recursive backtracking function dfs(currentWord, visited, depth):
    • If currentWord == endWord, return depth
    • For each word in wordList that is not visited:
      • If it differs from currentWord by exactly one letter:
        • Mark it as visited
        • Recursively call dfs(word, visited, depth + 1)
        • Track the minimum result
        • Unmark it (backtrack)
  4. Call dfs(beginWord, {beginWord}, 1) and return the minimum, or 0 if unreachable

Code

#include <vector>
#include <string>
#include <unordered_set>
#include <climits>
using namespace std;

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        if (wordSet.find(endWord) == wordSet.end()) return 0;
        
        unordered_set<string> visited;
        visited.insert(beginWord);
        int result = INT_MAX;
        
        dfs(beginWord, endWord, wordList, visited, 1, result);
        return result == INT_MAX ? 0 : result;
    }
    
private:
    bool differByOne(const string& a, const string& b) {
        int diff = 0;
        for (int i = 0; i < a.size(); i++) {
            if (a[i] != b[i]) diff++;
            if (diff > 1) return false;
        }
        return diff == 1;
    }
    
    void dfs(const string& current, const string& endWord,
             vector<string>& wordList, unordered_set<string>& visited,
             int depth, int& result) {
        if (current == endWord) {
            result = min(result, depth);
            return;
        }
        if (depth >= result) return; // pruning
        
        for (const string& word : wordList) {
            if (visited.find(word) == visited.end() && differByOne(current, word)) {
                visited.insert(word);
                dfs(word, endWord, wordList, visited, depth + 1, result);
                visited.erase(word);
            }
        }
    }
};
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: list[str]) -> int:
        word_set = set(wordList)
        if endWord not in word_set:
            return 0
        
        self.result = float('inf')
        visited = {beginWord}
        
        def differ_by_one(a: str, b: str) -> bool:
            diff = 0
            for i in range(len(a)):
                if a[i] != b[i]:
                    diff += 1
                    if diff > 1:
                        return False
            return diff == 1
        
        def dfs(current: str, depth: int):
            if current == endWord:
                self.result = min(self.result, depth)
                return
            if depth >= self.result:
                return  # pruning
            
            for word in wordList:
                if word not in visited and differ_by_one(current, word):
                    visited.add(word)
                    dfs(word, depth + 1)
                    visited.remove(word)
        
        dfs(beginWord, 1)
        return self.result if self.result != float('inf') else 0
import java.util.*;

class Solution {
    private int result = Integer.MAX_VALUE;
    
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(endWord)) return 0;
        
        Set<String> visited = new HashSet<>();
        visited.add(beginWord);
        dfs(beginWord, endWord, wordList, visited, 1);
        return result == Integer.MAX_VALUE ? 0 : result;
    }
    
    private boolean differByOne(String a, String b) {
        int diff = 0;
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) != b.charAt(i)) diff++;
            if (diff > 1) return false;
        }
        return diff == 1;
    }
    
    private void dfs(String current, String endWord, List<String> wordList,
                     Set<String> visited, int depth) {
        if (current.equals(endWord)) {
            result = Math.min(result, depth);
            return;
        }
        if (depth >= result) return;
        
        for (String word : wordList) {
            if (!visited.contains(word) && differByOne(current, word)) {
                visited.add(word);
                dfs(word, endWord, wordList, visited, depth + 1);
                visited.remove(word);
            }
        }
    }
}

Complexity Analysis

Time Complexity: O(N! × M)

In the worst case, the backtracking explores all possible orderings of words in the dictionary. For each word, we compare it character-by-character (M comparisons) against all N words. The total number of paths can be exponential — up to N! in pathological cases — making this approach extremely slow for large inputs.

Space Complexity: O(N × M)

The visited set can hold up to N words, each of length M. The recursion stack can go N levels deep in the worst case.

Why This Approach Is Not Efficient

The backtracking approach explores all possible transformation paths to find the shortest one. This means it might discover a path of length 10 first, then keep searching for shorter paths — wasting enormous effort on long paths that will never be the answer.

With N = 5000 words and M = 10, the number of possible paths is astronomical. DFS (depth-first search) inherently goes deep before going wide, so it finds long paths before short ones. There's no way to stop early when the first valid path is found because it might not be the shortest.

The fundamental insight is: when we want the shortest path in an unweighted graph, BFS (breadth-first search) is the right tool, not DFS. BFS explores all paths of length k before any path of length k+1, so the first time it reaches the target, that path is guaranteed to be the shortest. This eliminates the need to explore all paths.

Better Approach - BFS with Neighbor Comparison

Intuition

Since we need the shortest transformation sequence, BFS is the natural choice. BFS explores level by level: first all words reachable in 1 step, then all words reachable in 2 steps, and so on. The moment we reach endWord, we know we've found the shortest path.

Think of it like ripples spreading in a pond. You drop a stone at beginWord, and the ripple expands outward one step at a time. The first time the ripple touches endWord, that's the minimum number of steps.

In this approach, for each word we dequeue from BFS, we scan through the entire wordList to find all words that differ by exactly one letter. This is correct but does redundant work — comparing every pair of words at each BFS level.

Step-by-Step Explanation

Let's trace through with beginWord = "hit", endWord = "cog", wordList = ["hot", "dot", "dog", "lot", "log", "cog"]:

Step 1: Initialize. Put "hit" into the BFS queue. Mark "hit" as visited. Level = 1.

Step 2: Process level 1. Dequeue "hit". Scan entire wordList for words differing by one letter from "hit":

  • "hot": differs at position 1 only → neighbor! Enqueue "hot", mark visited.
  • "dot": 2 differences → skip
  • "dog": 3 differences → skip
  • "lot": 2 differences → skip
  • "log": 3 differences → skip
  • "cog": 3 differences → skip
    Level 1 done. Queue: ["hot"]. Level = 2.

Step 3: Process level 2. Dequeue "hot". Scan entire wordList for neighbors:

  • "dot": differs at position 0 only → neighbor! Enqueue, mark visited.
  • "dog": 2 differences → skip
  • "lot": differs at position 0 only → neighbor! Enqueue, mark visited.
  • "log": 2 differences → skip
  • "cog": 2 differences → skip
    Level 2 done. Queue: ["dot", "lot"]. Level = 3.

Step 4: Process level 3. Dequeue "dot". Scan wordList:

  • "hot": visited → skip
  • "dog": differs at position 2 → neighbor! Enqueue, mark visited.
  • "lot": differs at position 0 → neighbor but already visited → skip.
    Dequeue "lot". Scan wordList:
  • "hot": visited → skip
  • "dot": visited → skip
  • "log": differs at position 2 → neighbor! Enqueue, mark visited.
    Level 3 done. Queue: ["dog", "log"]. Level = 4.

Step 5: Process level 4. Dequeue "dog". Scan wordList:

  • "cog": differs at position 0 → neighbor! "cog" == endWord → FOUND!
    Return level + 1 = 4 + 1 = 5.

BFS Level-by-Level Exploration for Word Ladder — Watch how BFS explores all words at distance k before any word at distance k+1, guaranteeing the shortest path is found first.

Algorithm

  1. Place all words from wordList into a set for O(1) lookup
  2. If endWord is not in the set, return 0
  3. Initialize a queue with beginWord and set level = 1
  4. While the queue is not empty:
    a. Process all words at the current level (level-by-level BFS)
    b. For each dequeued word, scan the entire wordList
    c. For each word that differs by exactly one letter and is not visited:
    • If it equals endWord, return level + 1
    • Otherwise, mark visited and enqueue it
      d. Increment level
  5. Return 0 (no path found)

Code

#include <vector>
#include <string>
#include <unordered_set>
#include <queue>
using namespace std;

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        if (wordSet.find(endWord) == wordSet.end()) return 0;
        
        unordered_set<string> visited;
        visited.insert(beginWord);
        queue<string> q;
        q.push(beginWord);
        int level = 1;
        
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                string word = q.front();
                q.pop();
                
                for (const string& candidate : wordList) {
                    if (visited.count(candidate)) continue;
                    if (differByOne(word, candidate)) {
                        if (candidate == endWord) return level + 1;
                        visited.insert(candidate);
                        q.push(candidate);
                    }
                }
            }
            level++;
        }
        return 0;
    }
    
private:
    bool differByOne(const string& a, const string& b) {
        int diff = 0;
        for (int i = 0; i < a.size(); i++) {
            if (a[i] != b[i]) diff++;
            if (diff > 1) return false;
        }
        return diff == 1;
    }
};
from collections import deque

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: list[str]) -> int:
        word_set = set(wordList)
        if endWord not in word_set:
            return 0
        
        visited = {beginWord}
        queue = deque([beginWord])
        level = 1
        
        def differ_by_one(a: str, b: str) -> bool:
            diff = 0
            for i in range(len(a)):
                if a[i] != b[i]:
                    diff += 1
                    if diff > 1:
                        return False
            return diff == 1
        
        while queue:
            for _ in range(len(queue)):
                word = queue.popleft()
                for candidate in wordList:
                    if candidate in visited:
                        continue
                    if differ_by_one(word, candidate):
                        if candidate == endWord:
                            return level + 1
                        visited.add(candidate)
                        queue.append(candidate)
            level += 1
        
        return 0
import java.util.*;

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(endWord)) return 0;
        
        Set<String> visited = new HashSet<>();
        visited.add(beginWord);
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        int level = 1;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String word = queue.poll();
                for (String candidate : wordList) {
                    if (visited.contains(candidate)) continue;
                    if (differByOne(word, candidate)) {
                        if (candidate.equals(endWord)) return level + 1;
                        visited.add(candidate);
                        queue.offer(candidate);
                    }
                }
            }
            level++;
        }
        return 0;
    }
    
    private boolean differByOne(String a, String b) {
        int diff = 0;
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) != b.charAt(i)) diff++;
            if (diff > 1) return false;
        }
        return diff == 1;
    }
}

Complexity Analysis

Time Complexity: O(N² × M)

At each BFS level, for every word dequeued, we compare it against all N words in the wordList. Each comparison takes O(M) time (comparing character by character). In the worst case, BFS visits all N words, and for each we scan all N candidates, giving O(N² × M).

Space Complexity: O(N × M)

The visited set and queue can hold up to N words, each of length M.

Why This Approach Is Not Efficient

While BFS correctly finds the shortest path (a major improvement over backtracking), the bottleneck is how we find neighbors. For each word in the queue, we compare it against the entire wordList — that's O(N) comparisons per word.

With N = 5000 words of length M = 10, the BFS approach does up to 5000 × 5000 × 10 = 250 million character comparisons. This is too slow.

The key insight: instead of scanning all N words to find neighbors, we can generate all possible one-letter variations of the current word. Since each word has M positions and each position has 26 possible letters, we generate at most 26 × M candidate words and check if they exist in a set in O(M) time per lookup. For M = 10, that's only 260 candidates per word — far fewer than 5000 comparisons.

Optimal Approach - BFS with Character Substitution

Intuition

Instead of comparing the current word against every word in the dictionary, we generate all possible words that differ by one letter. For a word of length M, there are exactly 26 × M possible one-letter transformations (replace each of M positions with each of 26 letters). We check if each generated word exists in the dictionary using a hash set.

Think of it this way: instead of asking every person in a room "do you differ from me by one letter?", you write down all possible one-letter variations of your name on sticky notes and check the room's guest list for matches. If names are short (M ≤ 10), writing 260 sticky notes is much faster than asking 5000 people.

We also remove discovered words from the set immediately upon visiting them. This serves two purposes: it prevents revisiting (same as a visited set), and it shrinks the set over time, though the primary speedup comes from the generation strategy.

This approach keeps BFS's shortest-path guarantee while dramatically reducing the neighbor-finding cost from O(N × M) per word to O(26 × M × M) = O(M²) per word (since hash set lookup costs O(M) for a string of length M).

Step-by-Step Explanation

Let's trace with beginWord = "hit", endWord = "cog", wordList = ["hot", "dot", "dog", "lot", "log", "cog"]:

Step 1: Build a set from wordList: {"hot", "dot", "dog", "lot", "log", "cog"}. Check endWord "cog" is in set → yes. Initialize queue with "hit", level = 1.

Step 2: Process level 1. Dequeue "hit". Generate all one-letter variants:

  • Position 0: replace 'h' with a-z → "ait", "bit", ..., "dit", ..., "zit". Check set → none found.
  • Position 1: replace 'i' with a-z → "hat", "hbt", ..., "hot", ..., "hzt". Check set → "hot" found! Remove "hot" from set, enqueue it.
  • Position 2: replace 't' with a-z → "hia", "hib", ..., "hiz". Check set → none found.
    Level 1 done. Queue: ["hot"]. Set: {"dot", "dog", "lot", "log", "cog"}. Level = 2.

Step 3: Process level 2. Dequeue "hot". Generate variants:

  • Position 0: "aot".."zot" → "dot" found! Remove, enqueue. "lot" found! Remove, enqueue.
  • Position 1: "hat".."hzt" → none in set.
  • Position 2: "hoa".."hoz" → none in set.
    Level 2 done. Queue: ["dot", "lot"]. Set: {"dog", "log", "cog"}. Level = 3.

Step 4: Process level 3. Dequeue "dot". Generate variants:

  • Position 0: → none in set.
  • Position 1: → none in set.
  • Position 2: "doa".."doz" → "dog" found! Remove, enqueue.
    Dequeue "lot". Generate variants:
  • Position 0: → none.
  • Position 1: → none.
  • Position 2: "loa".."loz" → "log" found! Remove, enqueue.
    Level 3 done. Queue: ["dog", "log"]. Set: {"cog"}. Level = 4.

Step 5: Process level 4. Dequeue "dog". Generate variants:

  • Position 0: "aog".."zog" → "cog" found! "cog" == endWord → return level + 1 = 5.

Optimal BFS — Character Substitution Strategy — Watch how BFS with character substitution generates candidate words at each step instead of scanning the full dictionary, finding the shortest word ladder efficiently.

Algorithm

  1. Build a hash set from wordList for O(1) existence checks
  2. If endWord is not in the set, return 0
  3. Initialize a queue with beginWord, set level = 1
  4. While the queue is not empty:
    a. For each word at the current level:
    • Dequeue the word
    • For each position j from 0 to M-1:
      • For each letter c from 'a' to 'z':
        • Form a new word by replacing position j with c
        • If this new word equals endWord, return level + 1
        • If this new word exists in the set:
          • Remove it from the set (marks it visited)
          • Enqueue it
    • Restore the original character at position j
      b. Increment level
  5. Return 0 (no path found)

Code

#include <vector>
#include <string>
#include <unordered_set>
#include <queue>
using namespace std;

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        if (wordSet.find(endWord) == wordSet.end()) return 0;
        
        queue<string> q;
        q.push(beginWord);
        wordSet.erase(beginWord);
        int level = 1;
        
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                string word = q.front();
                q.pop();
                
                for (int j = 0; j < word.size(); j++) {
                    char original = word[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == original) continue;
                        word[j] = c;
                        
                        if (word == endWord) return level + 1;
                        
                        if (wordSet.find(word) != wordSet.end()) {
                            wordSet.erase(word);
                            q.push(word);
                        }
                    }
                    word[j] = original;
                }
            }
            level++;
        }
        return 0;
    }
};
from collections import deque

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: list[str]) -> int:
        word_set = set(wordList)
        if endWord not in word_set:
            return 0
        
        queue = deque([beginWord])
        word_set.discard(beginWord)
        level = 1
        
        while queue:
            for _ in range(len(queue)):
                word = queue.popleft()
                
                for j in range(len(word)):
                    original = word[j]
                    for c in 'abcdefghijklmnopqrstuvwxyz':
                        if c == original:
                            continue
                        candidate = word[:j] + c + word[j+1:]
                        
                        if candidate == endWord:
                            return level + 1
                        
                        if candidate in word_set:
                            word_set.remove(candidate)
                            queue.append(candidate)
            level += 1
        
        return 0
import java.util.*;

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(endWord)) return 0;
        
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        wordSet.remove(beginWord);
        int level = 1;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                char[] word = queue.poll().toCharArray();
                
                for (int j = 0; j < word.length; j++) {
                    char original = word[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == original) continue;
                        word[j] = c;
                        String candidate = new String(word);
                        
                        if (candidate.equals(endWord)) return level + 1;
                        
                        if (wordSet.contains(candidate)) {
                            wordSet.remove(candidate);
                            queue.offer(candidate);
                        }
                    }
                    word[j] = original;
                }
            }
            level++;
        }
        return 0;
    }
}

Complexity Analysis

Time Complexity: O(N × M² × 26) = O(N × M²)

Where N is the number of words in the wordList and M is the length of each word.

  • BFS visits at most N words (each removed from the set once)
  • For each word, we try M positions × 26 letters = 26M candidate words
  • Each candidate word creation and set lookup costs O(M) (string hashing)
  • Total: O(N × 26 × M × M) = O(N × M²)

For the given constraints (N ≤ 5000, M ≤ 10): 5000 × 100 × 26 = 13 million — well within time limits.

Space Complexity: O(N × M)

The hash set stores N words each of length M. The BFS queue can hold up to N words in the worst case.