Skip to main content

127. Word Ladder

hardAsked at HP

HP's network diagnostics and configuration management tools find shortest transition paths between device states — analogous to Word Ladder's shortest transformation sequence. HP uses this problem to test BFS shortest-path reasoning, graph construction from implicit adjacency, and the ability to prune search space efficiently.

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

Source citations

Public interview reports confirming this problem appears in HP loops.

  • Glassdoor (2025-Q3)— HP SWE senior rounds occasionally include Word Ladder as a BFS/graph construction hard problem.
  • Blind (2025-08)— HP interview prep threads mention Word Ladder as a demanding BFS problem for network-software and systems-software tracks.

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, and every si (1 ≤ i ≤ k) is in wordList. Given beginWord, endWord, and 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 (5 words).

Example 2

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

Explanation: cog is not in wordList — no valid transformation.

Approaches

1. BFS with wildcard pattern grouping

For each word, generate wildcard patterns (e.g., 'hit' → '*it', 'h*t', 'hi*'). Group words by pattern. BFS from beginWord, expanding to neighbors found via pattern lookup. Avoid revisiting words.

Time
O(M² × N) where M = word length, N = wordList size
Space
O(M² × N)
function ladderLength(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;
  // Build pattern → [words] map
  const patternMap = new Map();
  for (const word of [beginWord, ...wordList]) {
    for (let i = 0; i < word.length; 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]];
  while (queue.length) {
    const [word, length] = queue.shift();
    for (let i = 0; i < word.length; i++) {
      const pattern = word.slice(0, i) + '*' + word.slice(i + 1);
      for (const neighbor of (patternMap.get(pattern) || [])) {
        if (neighbor === endWord) return length + 1;
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push([neighbor, length + 1]);
        }
      }
    }
  }
  return 0;
}

Tradeoff: Pre-building the pattern map avoids checking all 25 letter substitutions per position per word at BFS time. Efficient for dense word lists.

2. BFS with direct substitution

For each BFS word, try all 26 × M substitutions, check if the result is in the word set, and if so, add to the queue. Simpler to implement.

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]);
  while (queue.length) {
    const [word, length] = queue.shift();
    for (let i = 0; i < word.length; i++) {
      for (let c = 97; c <= 122; c++) {
        const newWord = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
        if (newWord === endWord) return length + 1;
        if (wordSet.has(newWord) && !visited.has(newWord)) {
          visited.add(newWord);
          queue.push([newWord, length + 1]);
        }
      }
    }
  }
  return 0;
}

Tradeoff: Simpler code; O(26 × M × N) per BFS level. For short words and small dictionaries this is perfectly adequate. Pattern-based approach is better when M is large.

HP-specific tips

HP interviewers want you to articulate the graph construction: 'Each word is a node; an edge exists between words that differ by one letter. I need the shortest path, so I use BFS.' Mark words as visited when enqueuing, not when dequeuing — this prevents duplicate entries in the queue. The endWord check at the beginning saves time.

Common mistakes

  • Not checking if endWord is in wordList upfront — if it isn't, no valid path exists; return 0 immediately.
  • Marking words as visited when dequeuing instead of enqueuing — allows duplicate queue entries, blowing up time complexity.
  • Modifying the wordSet during BFS to mark visited words — use a separate visited set.
  • Returning length instead of length + 1 when endWord is found — the current length counts words processed so far; you need to add the endWord step.

Follow-up questions

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

  • Return all shortest transformation sequences (LC 126 — Word Ladder II) — backtrack from BFS layers.
  • What if you could change more than one letter at a time — how does the adjacency definition change?
  • Bidirectional BFS — how does it reduce search space for this problem?

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 is BFS correct here and not DFS?

BFS explores all paths of length k before any path of length k+1, guaranteeing the first time endWord is reached it's via the shortest path. DFS finds a path but not necessarily the shortest one.

Why mark visited when enqueuing?

If you mark when dequeuing, the same word can be enqueued multiple times before being dequeued. This can exponentially inflate the queue size in a dense graph.

What is bidirectional BFS and why does it help?

Run BFS from both beginWord and endWord simultaneously. When the two frontiers meet, the shortest path is found. This reduces the search space from O(b^d) to O(b^(d/2)), where b is branching factor and d is depth.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →