Course4all
Join us on telegram
Home/dsa/Graphs/Word Ladder

Word Ladder

Master this topic with zero to advance depth.

Word Ladder

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words such that:

  • Every adjacent pair of words differs by a single letter.
  • Every s_i for 1 <= i <= k is in wordList.
  • s_k == endWord.

Return the number of words in the shortest transformation sequence, or 0 if no such sequence exists.

Visual Representation

Begin: "hit", End: "cog", List: ["hot","dot","dog","lot","log","cog"] "hit" -> "hot" -> "dot" -> "dog" -> "cog" Path length: 5
Hard

Examples

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

hit -> hot -> dot -> dog -> cog (5 words).

Approach 1

Level I: Brute Force (BFS with Word Comparison)

Intuition

The simplest BFS approach is to compare the current word with every word in the dictionary to find neighbors (words with only 1 character difference).

Thought Process

  1. Use a Queue for BFS, starting with (beginWord, 1).
  2. In each step:
    • Pop word, dist.
    • Iterate through every w in wordList:
      • If w is not visited and isNeighbor(word, w):
        • If w == endWord, return dist + 1.
        • Mark w as visited and add to queue.

Why it's Level I

If NN is the number of words, this involves O(N)O(N) comparisons for every word we visit, leading to O(N2)O(N^2) total work.

⏱ O(N^2 * M) - Where N is word list size and M is word length.💾 O(N) - To store visited set.

Detailed Dry Run

"hit" -> "cog", ["hot", "dot", "dog", "cog"]

  1. "hit": neighbors? Scan list. Found "hot".
  2. "hot": neighbors? Scan list. Found "dot", "lot".
  3. "dot": neighbors? Scan list. Found "dog".
  4. "dog": neighbors? Scan list. Found "cog". DONE.
java
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> set = new HashSet<>(wordList);
        if (!set.contains(endWord)) return 0;
        Queue<Object[]> q = new LinkedList<>();
        q.add(new Object[]{beginWord, 1});
        Set<String> vis = new HashSet<>();
        vis.add(beginWord);
        while (!q.isEmpty()) {
            Object[] curr = q.poll();
            String word = (String) curr[0];
            int dist = (int) curr[1];
            if (word.equals(endWord)) return dist;
            for (String w : set) {
                if (!vis.contains(w) && isNbr(word, w)) {
                    vis.add(w); q.add(new Object[]{w, dist + 1});
                }
            }
        }
        return 0;
    }
    private boolean isNbr(String s1, String s2) {
        int diff = 0;
        for (int i = 0; i < s1.length(); i++) if (s1.charAt(i) != s2.charAt(i)) if (++diff > 1) return false;
        return diff == 1;
    }
}
Approach 2

Level III: Optimal (BFS with Char Change)

Intuition

Instead of comparing with every word, we can generate all 26 possible neighbors for each character position. This is much faster when the alphabet size is small.

Thought Process

  1. Store all words in a set for O(1)O(1) lookups.
  2. Use a Queue for BFS, starting with (beginWord, 1).
  3. While the queue is not empty:
    • Pop word, dist.
    • For each character position ii in word:
      • Replace word[i] with every letter from 'a' to 'z'.
      • If the new string exists in the set:
        • If it's the endWord, return dist + 1.
        • Add to queue and remove from set (marking it visited).

Pattern: BFS State Generation

⏱ O(M * 26 * N) - Usually much faster than O(N^2 * M).💾 O(N * M) - To store the word set.

Detailed Dry Run

hit -> hot -> dot -> dog -> cog

  • hit: change h to i,j,k... change i to a,b,c... change t to a,b,c,s,o (hot!)
  • Add hot to queue, remove from set.
  • Process 'hot' similarly.
java
import java.util.*;

public class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> set = new HashSet<>(wordList);
        if (!set.contains(endWord)) return 0;
        Queue<String> q = new LinkedList<>();
        q.offer(beginWord);
        int level = 1;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                String curr = q.poll();
                if (curr.equals(endWord)) return level;
                char[] chars = curr.toCharArray();
                for (int j = 0; j < chars.length; j++) {
                    char orig = chars[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        chars[j] = c;
                        String next = new String(chars);
                        if (set.contains(next)) {
                            q.offer(next);
                            set.remove(next);
                        }
                    }
                    chars[j] = orig;
                }
            }
            level++;
        }
        return 0;
    }
}
← Previous QuestionCheapest Flights Within K Stops
Next Question →Shortest Path in Binary Matrix