Skip to main content

127. Word Ladder

hardAsked at Akamai

Find the shortest transformation sequence from one word to another changing one letter at a time. Akamai ties this to BFS in routing graphs — finding the minimum number of hops between two network states where each hop changes exactly one configuration parameter is the same shortest-path problem on an implicit graph.

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

Source citations

Public interview reports confirming this problem appears in Akamai loops.

  • Glassdoor (2025-12)— Akamai senior SWE reports mention Word Ladder as a graph BFS problem used in algorithm-heavy onsite rounds.
  • Blind (2025-09)— Akamai threads list this as a problem where the implicit graph construction and BFS level-tracking are explicitly evaluated.

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 si-1 and si differs by exactly one 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 (5 words in sequence).

Example 2

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

Explanation: endWord 'cog' is not in wordList — no valid path.

Approaches

1. BFS with wildcard pattern pre-processing

Build an adjacency map: for each word, replace each character with '*' to create a wildcard pattern. Words sharing a pattern differ by exactly one letter. BFS from beginWord, expanding via shared patterns. Count levels until endWord is reached.

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

Tradeoff: O(M² * N) where M = word length, N = dict size. Pre-computing patterns avoids trying all 26 letter substitutions per position at BFS time. The pattern map is the key optimization.

2. BFS with direct neighbor generation

For each word in the BFS queue, try replacing each character with a-z. If the resulting word is in the dictionary and unvisited, add it to the next level.

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

Tradeoff: O(M * 26 * N) — simpler to explain, slightly different constant factor. The pattern approach scales better for large word lists because neighbor lookups are O(1) from the map.

Akamai-specific tips

Frame this as a shortest-path problem on an implicit graph immediately: 'Each word is a node. Two nodes are connected if they differ by exactly one letter. I need the shortest path from beginWord to endWord — that is BFS.' Akamai interviewers expect this graph framing before any code. Then justify BFS over DFS: 'BFS guarantees the shortest path in an unweighted graph; DFS would find a path but not necessarily the shortest one.'

Common mistakes

  • Using DFS instead of BFS — DFS does not guarantee shortest path.
  • Not checking if endWord is in wordList — if it is absent, return 0 immediately; the problem requires the end word to be in the dictionary.
  • Counting edges instead of nodes — the problem asks for the number of words in the sequence, not the number of transformations. Off-by-one: start at level 1 (beginWord counts as word 1).

Follow-up questions

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

  • Word Ladder II (LC 126) — return all shortest transformation sequences, not just the count.
  • How would bidirectional BFS reduce the search space?
  • What if words can differ by up to k letters per step — how does the graph structure change?

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 does BFS guarantee the shortest path?

BFS explores all nodes at distance d before any node at distance d+1. The first time endWord is reached, it is via the shortest possible path. DFS does not have this property.

What is the benefit of bidirectional BFS?

Instead of searching from beginWord to endWord, you simultaneously search from both ends. The two frontiers meet in the middle, reducing 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 Akamai interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →