Skip to main content

127. Word Ladder

hardAsked at Cisco

Word Ladder at Cisco is a graph-BFS problem where the graph isn't given to you — you have to construct the implicit edges by recognizing 'two words are adjacent iff they differ by exactly one letter.' The interviewer is checking whether you build the adjacency on-the-fly using a wildcard pattern trick to keep edges fast.

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

Source citations

Public interview reports confirming this problem appears in Cisco loops.

  • Glassdoor (2026-Q1)— Cisco SDE-III onsite reports cite Word Ladder as the hardest graph round.
  • Blind (2025-08)— Cisco interview thread lists this as a recurring BFS problem for backend roles.

Problem

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words 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 (beginWord does not need to be in wordList), and sk == endWord. 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. Returns the count of words in the chain.

Example 2

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

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

Approaches

1. Brute-force BFS, compare every pair to find neighbors

Standard BFS. For each word dequeued, scan the dictionary and find every word that differs by one letter — those are the neighbors.

Time
O(N^2 * L)
Space
O(N * L)
function ladderLengthBrute(beginWord, endWord, wordList) {
  const set = new Set(wordList);
  if (!set.has(endWord)) return 0;
  const queue = [[beginWord, 1]];
  const visited = new Set([beginWord]);
  function differByOne(a, b) {
    let diff = 0;
    for (let i = 0; i < a.length; i++) if (a[i] !== b[i]) diff++;
    return diff === 1;
  }
  while (queue.length) {
    const [word, dist] = queue.shift();
    if (word === endWord) return dist;
    for (const next of set) {
      if (!visited.has(next) && differByOne(word, next)) {
        visited.add(next);
        queue.push([next, dist + 1]);
      }
    }
  }
  return 0;
}

Tradeoff: Quadratic in the dictionary size because each dequeue scans every word. Fails on the LeetCode constraint upper bound (5000 words). Useful to show you understand the BFS shell before optimizing.

2. BFS with wildcard pattern map (optimal)

Preprocess: for each word, generate L wildcard patterns (one per position, e.g., 'hit' -> '*it', 'h*t', 'hi*'). Group words by pattern. Now neighbors are O(L) to find: just look up each wildcard pattern.

Time
O(N * L^2)
Space
O(N * L^2)
function ladderLength(beginWord, endWord, wordList) {
  const set = new Set(wordList);
  if (!set.has(endWord)) return 0;
  const L = beginWord.length;
  const patternMap = new Map();
  for (const word of 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 queue = [[beginWord, 1]];
  const visited = new Set([beginWord]);
  while (queue.length) {
    const [word, dist] = queue.shift();
    if (word === endWord) return dist;
    for (let i = 0; i < L; i++) {
      const pattern = word.slice(0, i) + '*' + word.slice(i + 1);
      for (const next of patternMap.get(pattern) || []) {
        if (!visited.has(next)) {
          visited.add(next);
          queue.push([next, dist + 1]);
        }
      }
    }
  }
  return 0;
}

Tradeoff: L^2 because each word generates L patterns, each O(L) to construct. But N * L^2 with N=5000 and L=10 is 500k ops — comfortably within constraints. This is what Cisco wants on the whiteboard.

3. Bidirectional BFS

Run BFS from both ends and stop when the two frontiers meet. Cuts the search space dramatically when paths are long.

Time
O(N * L^2)
Space
O(N * L^2)
function ladderLengthBi(beginWord, endWord, wordList) {
  const set = new Set(wordList);
  if (!set.has(endWord)) return 0;
  const L = beginWord.length;
  const patternMap = new Map();
  for (const word of wordList) {
    for (let i = 0; i < L; i++) {
      const p = word.slice(0, i) + '*' + word.slice(i + 1);
      if (!patternMap.has(p)) patternMap.set(p, []);
      patternMap.get(p).push(word);
    }
  }
  let front = new Set([beginWord]);
  let back = new Set([endWord]);
  const visited = new Set([beginWord, endWord]);
  let dist = 1;
  while (front.size && back.size) {
    if (front.size > back.size) [front, back] = [back, front];
    const next = new Set();
    for (const word of front) {
      for (let i = 0; i < L; i++) {
        const p = word.slice(0, i) + '*' + word.slice(i + 1);
        for (const nb of patternMap.get(p) || []) {
          if (back.has(nb)) return dist + 1;
          if (!visited.has(nb)) {
            visited.add(nb);
            next.add(nb);
          }
        }
      }
    }
    front = next;
    dist++;
  }
  return 0;
}

Tradeoff: Same Big-O but the constants are far better on long paths because each side only explores depth/2. Cisco interviewers love this as a follow-up — say 'I'd swap to bidirectional BFS for very long words where the path could be many hops.'

Cisco-specific tips

Cisco interviewers grade this on TWO things: (1) you recognize this is BFS on an implicit graph (not 'try every transformation'), and (2) you build the wildcard pattern map BEFORE the BFS so neighbor lookup is O(L) instead of O(N). Say out loud: 'I'll preprocess a wildcard-pattern map so that neighbors of any word are O(L) to find — that gets the total BFS to O(N * L^2).' That sentence is the entire interview signal.

Common mistakes

  • Building neighbors by scanning the whole dictionary inside the BFS loop — that's O(N^2) and TLEs on the LeetCode upper bound.
  • Forgetting to check if `endWord` is in the dictionary up front — saves a full BFS on the unreachable case.
  • Counting edges instead of nodes — the answer is the length of the sequence (count of words), not the number of transformations.

Follow-up questions

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

  • Word Ladder II (LC 126) — return ALL shortest paths. BFS layers + reverse-walk via parent pointers.
  • Open the Lock (LC 752) — same BFS-on-implicit-graph pattern but the graph is a 4-digit combination space.
  • Minimum Genetic Mutation (LC 433) — identical pattern with the alphabet {A,C,G,T}.
  • What if words can also differ by INSERTION or DELETION? (Edit distance — different algorithm.)

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 the wildcard pattern trick instead of trying all 26 letter swaps?

Trying all 26 swaps at each position is O(26 * L) per word, then checking dictionary membership is O(1) — total O(N * L * 26). The wildcard pattern approach is O(N * L^2) and is more general (it works for any alphabet size). For lowercase English (26 letters), the all-letter-swap version is actually slightly faster — bring it up as the alternative.

Is bidirectional BFS overkill?

For the LeetCode constraints (N=5000, L=10) plain BFS is comfortably fast enough. Bidirectional BFS shines when N or L grows and the path length stays moderate. Mention it as the production answer; Cisco interviewers love the awareness.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →