Skip to main content

127. Word Ladder

hardAsked at Cohere

Find the shortest transformation sequence from one word to another, changing one letter at a time. Cohere asks this because BFS over an implicit graph is the same reasoning used to find shortest edit-distance paths between token sequences in vocabulary-constrained generation.

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

Source citations

Public interview reports confirming this problem appears in Cohere loops.

  • Glassdoor (2025-Q4)— Cohere senior SWE candidates report Word Ladder as a hard graph-BFS problem with an NLP framing in onsites.
  • Blind (2025-09)— Mentioned in Cohere prep threads as a problem that tests implicit graph construction and BFS shortest-path reasoning.

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 exactly one letter, and 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).

Example 2

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

Explanation: endWord "cog" not in wordList — no path exists.

Approaches

1. BFS with pattern pre-processing

Pre-group words by wildcard patterns (e.g., 'h*t' → [hit, hot]). BFS from beginWord; at each step explore all words sharing a pattern with the current word. Track visited words to avoid cycles.

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

Tradeoff: O(M × 26 × N) per BFS level — in practice M is small (≤ 10) so 26M character substitutions per node is fast. The simplest correct BFS approach.

2. Bidirectional BFS

Run BFS simultaneously from both beginWord and endWord. Alternate expanding the smaller frontier. Stop when the two frontiers meet.

Time
O(M × 26 × N / 2) practical speedup
Space
O(N)
function ladderLength(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;
  let front = new Set([beginWord]), back = new Set([endWord]);
  let steps = 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 < word.length; i++) {
        for (let c = 97; c <= 122; c++) {
          const nb = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
          if (back.has(nb)) return steps + 1;
          if (wordSet.has(nb)) { next.add(nb); wordSet.delete(nb); }
        }
      }
    }
    front = next;
    steps++;
  }
  return 0;
}

Tradeoff: Dramatically reduces explored nodes in practice by meeting in the middle. Preferred for large wordLists. The swap to always expand the smaller frontier keeps both sides balanced.

Cohere-specific tips

Cohere teams think about edit distance and vocabulary constraints in language modelling contexts. Frame your solution: 'I am doing BFS on an implicit graph where nodes are words and edges connect words that differ by one character — this finds the shortest edit path under vocabulary constraints.' The bidirectional BFS is a strong signal for senior roles at Cohere. Mention that the same technique applies to bidirectional shortest-path search in knowledge graphs used in retrieval.

Common mistakes

  • Not checking if endWord is in wordList before starting BFS — can return a path that ends with a word not in the dictionary.
  • Not marking words as visited — the same word can be enqueued multiple times, exponentiating the BFS frontier.
  • Counting edges (transformations) instead of nodes (words) — the problem asks for the length of the sequence, which is edges + 1.
  • In bidirectional BFS, not deleting visited words from wordSet — prevents re-enqueuing from the opposite frontier.

Follow-up questions

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

  • Word Ladder II (LC 126) — return all shortest transformation sequences.
  • Minimum Genetic Mutation (LC 433) — same BFS on a 4-character alphabet.
  • How would you extend this to find shortest vocabulary-constrained paths in a semantic knowledge graph?

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?

BFS guarantees the shortest path. DFS finds a path but not necessarily the shortest one without exhaustive search.

Why enumerate all 26 character substitutions instead of comparing against all wordList words?

Substitution enumeration is O(26M) per word; comparing against all N words is O(NM). For large N, substitution enumeration is significantly faster.

Why does bidirectional BFS help?

In unidirectional BFS the frontier grows exponentially in the worst case. Bidirectional BFS caps the frontier size to roughly the square root of the full search space, giving a practical 2x–100x speedup.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →