Stage 2: Recursive Thinking·Graphs: BFS & DFS

Hard#1278 min readGraphsBFSShortest PathHashingLeetCode

Word Ladder

BFS on an implicit word graph, with wildcard buckets

BFS on an implicit graph. Each word is a node, edges connect words differing by one letter.

Published Apr 16, 2026

Problem

Given two words beginWord and endWord and a wordList, return the length of the shortest transformation sequence from beginWord to endWord such that:

Each transformed word differs from the previous by exactly one letter.
Each intermediate word exists in wordList.
Return 0 if no sequence exists.

The length counts words in the sequence (including both endpoints).

Input

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

Output

Explanation

hit → hot → dot → dog → cog (5 words).

Input

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

Output

Explanation

"cog" is not in the list, so no valid final step.

Intuition

This is the shortest-path problem on a graph where nodes are words and edges connect words that differ by exactly one letter. We want the minimum number of edges + 1.

BFS from beginWord solves shortest-path in unweighted graphs in O(V + E). The tricky part is computing the edges efficiently. The naive approach — for every pair of words, count differing characters — is O(N² · L) and timeouts on big inputs.

The wildcard bucket trick cuts this to O(N · L²) edges: for each word in the list, generate L patterns by replacing one character at a time with * (e.g. "hot" → "*ot", "h*t", "ho*"). Words that share any pattern differ by exactly one letter. The bucket pattern → [words] becomes the adjacency representation we need.

Bidirectional BFS further halves the depth: run BFS from both ends, alternating the smaller frontier, and stop when they meet. Reduces worst-case cost from b^d to 2 · b^(d/2) where b is branching factor.

Approach

BFS with wildcard buckets

TimeO(N·L²)

SpaceO(N·L²)

Recommended

Build a map pattern → [words] where each pattern has one wildcard.
Standard BFS from beginWord. For each current word, generate its L patterns; each pattern buckets points to ≤ N words. Push unvisited ones.
Stop when endWord is popped; return the level count.

use std::collections::{HashMap, HashSet, VecDeque};

impl Solution {
    pub fn ladder_length(
        begin_word: String,
        end_word: String,
        word_list: Vec<String>,
    ) -> i32 {
        let word_set: HashSet<String> = word_list.iter().cloned().collect();
        if !word_set.contains(&end_word) {
            return 0;
        }
        let l = begin_word.len();
        let mut buckets: HashMap<String, Vec<String>> = HashMap::new();
        for w in word_set.iter() {
            let bytes = w.as_bytes();
            for i in 0..l {
                let mut key: Vec<u8> = bytes.to_vec();
                key[i] = b'*';
                buckets
                    .entry(String::from_utf8(key).unwrap())
                    .or_insert_with(Vec::new)
                    .push(w.clone());
            }
        }
        let mut visited: HashSet<String> = HashSet::new();
        let mut q: VecDeque<(String, i32)> = VecDeque::new();
        q.push_back((begin_word.clone(), 1));
        visited.insert(begin_word);
        while let Some((w, steps)) = q.pop_front() {
            if w == end_word {
                return steps;
            }
            let bytes = w.as_bytes();
            for i in 0..l {
                let mut key: Vec<u8> = bytes.to_vec();
                key[i] = b'*';
                let k = String::from_utf8(key).unwrap();
                if let Some(list) = buckets.get(&k) {
                    for nb in list {
                        if !visited.contains(nb) {
                            visited.insert(nb.clone());
                            q.push_back((nb.clone(), steps + 1));
                        }
                    }
                }
            }
        }
        0
    }
}

Rust · runnable

function ladderLength(
  beginWord: string,
  endWord: string,
  wordList: string[]
): number {
  const words = new Set(wordList);
  if (!words.has(endWord)) return 0;
  const L = beginWord.length;
  const buckets = new Map<string, string[]>();
  for (const w of words) {
    for (let i = 0; i < L; i++) {
      const key= w.slice(0, i) + '*' + w.slice(i + 1);
      if (!buckets.has(key)) buckets.set(key, []);
      buckets.get(key)!.push(w);
    }
  }
  const visited= new Set<string>([beginWord]);
  const q: [string, number][] = [[beginWord, 1]];
  let head = 0;
  while (head < q.length) {
    const [w, steps]= q[head++];
    if (w= endWord) return steps;
    for (let i= 0; i < L; i++) {
      const key= w.slice(0, i) + '*' + w.slice(i + 1);
      const list= buckets.get(key);
      if (!list) continue;
      for (const nb of list) {
        if (visited.has(nb)) continue;
        visited.add(nb);
        q.push([nb, steps + 1]);
      }
    }
  }
  return 0;
}

TypeScript · runnable

Bidirectional BFS

TimeO(N·L²)

SpaceO(N·L²)

Maintain two frontiers — one from beginWord, one from endWord. Always expand the smaller one; if a newly visited word is already in the other frontier, we've met in the middle. The total depth to meet is halved.

This usually wins on dense word lists with long solutions. On tiny inputs the overhead of two frontiers makes it slower; benchmark if it matters.

use std::collections::{HashMap, HashSet};

impl Solution {
    pub fn ladder_length(
        begin_word: String,
        end_word: String,
        word_list: Vec<String>,
    ) -> i32 {
        let words: HashSet<String> = word_list.iter().cloned().collect();
        if !words.contains(&end_word) {
            return 0;
        }
        let l = begin_word.len();
        let mut buckets: HashMap<String, Vec<String>> = HashMap::new();
        for w in words.iter() {
            let bytes = w.as_bytes();
            for i in 0..l {
                let mut key: Vec<u8> = bytes.to_vec();
                key[i] = b'*';
                buckets
                    .entry(String::from_utf8(key).unwrap())
                    .or_insert_with(Vec::new)
                    .push(w.clone());
            }
        }
        let mut front: HashSet<String> = HashSet::from([begin_word.clone()]);
        let mut back: HashSet<String> = HashSet::from([end_word.clone()]);
        let mut seen: HashSet<String> = HashSet::from([begin_word, end_word]);
        let mut steps = 1;
        while !front.is_empty() && !back.is_empty() {
            if front.len() > back.len() {
                std::mem::swap(&mut front, &mut back);
            }
            let mut next: HashSet<String> = HashSet::new();
            for w in front.iter() {
                let bytes = w.as_bytes();
                for i in 0..l {
                    let mut key: Vec<u8> = bytes.to_vec();
                    key[i] = b'*';
                    let k = String::from_utf8(key).unwrap();
                    if let Some(list) = buckets.get(&k) {
                        for nb in list {
                            if back.contains(nb) {
                                return steps + 1;
                            }
                            if seen.insert(nb.clone()) {
                                next.insert(nb.clone());
                            }
                        }
                    }
                }
            }
            front = next;
            steps += 1;
        }
        0
    }
}

Rust · runnable

function ladderLength(
  beginWord: string,
  endWord: string,
  wordList: string[]
): number {
  const words = new Set(wordList);
  if (!words.has(endWord)) return 0;
  const L = beginWord.length;
  const buckets = new Map<string, string[]>();
  for (const w of words) {
    for (let i = 0; i < L; i++) {
      const key= w.slice(0, i) + '*' + w.slice(i + 1);
      if (!buckets.has(key)) buckets.set(key, []);
      buckets.get(key)!.push(w);
    }
  }
  let front= new Set<string>([beginWord]);
  let back = new Set<string>([endWord]);
  const seen = new Set<string>([beginWord, endWord]);
  let steps = 1;
  while (front.size > 0 && back.size > 0) {
    if (front.size > back.size) [front, back] = [back, front];
    const next = new Set<string>();
    for (const w of front) {
      for (let i = 0; i < L; i++) {
        const key= w.slice(0, i) + '*' + w.slice(i + 1);
        const list= buckets.get(key);
        if (!list) continue;
        for (const nb of list) {
          if (back.has(nb)) return steps + 1;
          if (!seen.has(nb)) {
            seen.add(nb);
            next.add(nb);
          }
        }
      }
    }
    front= next;
    steps++;
  }
  return 0;
}

TypeScript · runnable

Trace

Single-ended BFS on hit → cog with list ["hot","dot","dog","lot","log","cog"]:

level	popped	bucket matches	queued	visited size
1	hit	it, ht, hi*	hot	2
2	hot	ot, ht, ho*	dot, lot	4
3	dot / lot	ot, dt, do, ot, lt, lo	dog, log	6
4	dog / log	do, dg, og, lo, lg, og	cog	7
5	cog	(target, return 5)	-	-

Five words in the shortest chain.

Edge cases

endWord not in list — return 0 immediately; avoids useless BFS.
beginWord == endWord — problem constraints usually forbid this; if you hit it, returning 0 or 1 depends on interpretation (LeetCode excludes it).
No path exists — BFS exhausts without meeting; return 0.
Long words, small list — wildcard buckets are still O(N · L); the L² factor is per BFS, not per bucket build.

Takeaway

When the graph is implicit, the first question is "how do I generate edges without blowing up time?" The wildcard bucket trick is a pattern that shows up whenever neighbors are defined by "one step away" — single-letter change, single-digit change, single-bit flip. Precompute the bucketed adjacency once, then run a standard BFS on top.

Medium#994

Rotting Oranges

Multi-source BFS. All rotten oranges start in the queue simultaneously.

Medium#200

Number of Islands

Flood fill with DFS. The grid IS the graph — each cell is a node.

Medium#133

Clone Graph

BFS/DFS with a visited HashMap that maps old → new nodes.