Skip to main content

127. Word Ladder

hardAsked at HubSpot

HubSpot asks Word Ladder to test BFS on an implicit graph where nodes are words and edges are single-character transformations — a pattern that generalizes to shortest-path problems across their CRM entity relationship graph.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in HubSpot loops.

  • Glassdoor (2026-Q1)— HubSpot SWE senior-level interview reports list Word Ladder as a BFS graph problem requiring implicit graph construction.
  • Blind (2025-10)— HubSpot interview threads cite Word Ladder as an occasional hard problem testing BFS shortest-path in implicit graphs.

Problem

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence beginWord -> s1 -> s2 -> ... -> sk such that: every adjacent pair of words differs by a single letter; every si for 1 <= i <= k is in wordList. Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

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

Examples

Example 1

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

Explanation: hit → hot → dot → dog → cog is one shortest path of length 5.

Example 2

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

Explanation: endWord 'cog' is not in the wordList, so no transformation exists.

Approaches

1. BFS with wildcard pattern grouping

Preprocess wordList into a map of wildcard patterns to words (e.g., 'h*t' → ['hit', 'hot']). BFS from beginWord: for each word, generate all wildcard patterns, look up neighbors, and enqueue unvisited ones. Return the BFS level count when endWord is reached.

Time
O(M² × N) where M is word length and N is wordList size
Space
O(M² × N)
function ladderLength(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;
  const M = beginWord.length;
  // Precompute wildcard map
  const patternMap = new Map();
  for (const word of [beginWord, ...wordList]) {
    for (let i = 0; i < M; i++) {
      const pattern = word.slice(0, i) + '*' + word.slice(i + 1);
      if (!patternMap.has(pattern)) patternMap.set(pattern, []);
      patternMap.get(pattern).push(word);
    }
  }
  const visited = new Set([beginWord]);
  const queue = [[beginWord, 1]]; // [word, depth]
  let head = 0;
  while (head < queue.length) {
    const [word, depth] = queue[head++];
    for (let i = 0; i < M; i++) {
      const pattern = word.slice(0, i) + '*' + word.slice(i + 1);
      for (const neighbor of patternMap.get(pattern) || []) {
        if (neighbor === endWord) return depth + 1;
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push([neighbor, depth + 1]);
        }
      }
    }
  }
  return 0;
}

Tradeoff: Avoids comparing every word pair on every BFS step. The wildcard map groups words by transformation potential, reducing neighbor lookup. This is the approach preferred for large wordLists.

2. BFS with direct neighbor generation

For each word in the queue, try replacing each character with a-z and check if the result is in the word set. If unvisited, enqueue it.

Time
O(M × 26 × N)
Space
O(N)
function ladderLength(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;
  const queue = [[beginWord, 1]];
  const visited = new Set([beginWord]);
  let head = 0;
  while (head < queue.length) {
    const [word, depth] = queue[head++];
    for (let i = 0; i < word.length; i++) {
      for (let c = 0; c < 26; c++) {
        const ch = String.fromCharCode(97 + c);
        if (ch === word[i]) continue;
        const next = word.slice(0, i) + ch + word.slice(i + 1);
        if (next === endWord) return depth + 1;
        if (wordSet.has(next) && !visited.has(next)) {
          visited.add(next);
          queue.push([next, depth + 1]);
        }
      }
    }
  }
  return 0;
}

Tradeoff: Simpler to implement. O(M × 26 × N) — slightly different from wildcard approach but both are polynomial. Preferred for smaller word lists and cleaner interview code. Check endWord early (before enqueuing) to avoid processing it.

HubSpot-specific tips

Frame this as an unweighted shortest-path problem: 'Words are nodes; two words are connected if they differ by exactly one character. BFS gives the shortest path.' HubSpot interviewers value the BFS framing over iterative deepening. Mention the early termination: check if endWord is in wordList first (O(1) set lookup) to short-circuit immediately. For the direct approach, string slicing in JavaScript is O(M) per character swap — acknowledge this in your complexity analysis.

Common mistakes

  • Using DFS instead of BFS — DFS finds A path, not the SHORTEST path.
  • Not removing visited words from wordSet or tracking them separately — causes infinite loops and exponential time.
  • Checking if endWord is reachable only at BFS termination instead of early-returning when endWord is dequeued — wastes one BFS level.
  • Off-by-one in the return value — the length counts beginWord as step 1, so the sequence includes beginWord.

Follow-up questions

An interviewer at HubSpot may pivot to one of these next:

  • Word Ladder II (LC 126) — return all shortest transformation sequences (not just the count).
  • Bidirectional BFS — expand from both beginWord and endWord simultaneously, halving the search space.
  • How would you speed this up if the word list has 100,000 entries?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why BFS and not DFS for shortest path?

BFS explores nodes level by level (by hop count). The first time it reaches endWord is guaranteed to be the shortest path. DFS finds any path but not necessarily the shortest.

Why check if endWord is in wordList first?

If endWord isn't in the dictionary, no transformation sequence exists by definition. This O(1) check avoids a full BFS traversal for an impossible input.

What does the return value represent?

The number of words in the sequence, including both beginWord and endWord. A direct one-step transformation returns 2, not 1.

Practice these live with InterviewChamp.AI

Drill Word Ladder and other HubSpot interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →