Skip to main content

127. Word Ladder

hardAsked at Juniper Networks

Find the shortest word transformation sequence using BFS on an implicit graph. Juniper directly applies shortest-path BFS to routing: finding the minimum-hop path between two network nodes where each hop changes exactly one attribute (interface, AS number, VLAN) is the same implicit-graph BFS problem.

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

Source citations

Public interview reports confirming this problem appears in Juniper Networks loops.

  • Glassdoor (2025-Q3)— Cited in Juniper SWE onsite reports as a BFS/shortest-path hard problem with direct networking parallels.
  • Blind (2025-09)— Juniper interview prep threads list Word Ladder as a BFS hard problem asked in networking software 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, 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 (5 words, 4 transformations).

Example 2

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

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

Approaches

1. BFS with wildcard pattern neighbors

BFS from beginWord. Generate all neighbor words by replacing each character with 'a'-'z' and checking the word set. Each BFS level increments the transformation count. Return count when endWord is found.

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]]; // [currentWord, level]
  const visited = new Set([beginWord]);
  while (queue.length) {
    const [word, level] = 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 level + 1;
        if (wordSet.has(next) && !visited.has(next)) {
          visited.add(next);
          queue.push([next, level + 1]);
        }
      }
    }
  }
  return 0;
}

Tradeoff: O(M² * N) time. The wildcard neighbor generation avoids building an explicit adjacency list. BFS guarantees the shortest path. Check visited when enqueuing (not dequeuing) to avoid redundant enqueues.

2. Bidirectional BFS

Run BFS simultaneously from both beginWord and endWord. Expand the smaller frontier each step. When the frontiers intersect, the level sum is the answer. Reduces the search space from O(b^d) to O(b^(d/2)) where b = branching factor and d = depth.

Time
O(M² * N)
Space
O(M² * 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 level = 1;
  while (front.size && back.size) {
    // Always expand the smaller frontier
    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 candidate = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
          if (back.has(candidate)) return level + 1;
          if (wordSet.has(candidate)) {
            next.add(candidate);
            wordSet.delete(candidate); // mark visited
          }
        }
      }
    }
    front = next;
    level++;
  }
  return 0;
}

Tradeoff: Dramatically faster in practice for large graphs. Juniper interviewers in networking roles may specifically ask for bidirectional BFS — it mirrors how BGP route convergence works from both source and destination AS perspectives.

Juniper Networks-specific tips

State BFS immediately — this is a shortest-path problem and BFS is the correct algorithm. The implicit graph structure (each word is a node, edges connect one-letter-apart words) is worth stating explicitly: 'I'm building an implicit graph where edges connect words that differ by exactly one character.' Juniper interviewers appreciate the bidirectional BFS optimization and may specifically probe it. Connect to OSPF: 'SPF computation in OSPF is the same Dijkstra/BFS shortest-path problem on the link-state graph.'

Common mistakes

  • Not checking if endWord is in wordList early — return 0 immediately if it is absent.
  • Marking words as visited when dequeuing instead of enqueuing — allows the same word to be enqueued multiple times, blowing up the queue.
  • Not deleting visited words from the wordSet in bidirectional BFS — they can be re-added to the opposite frontier.
  • Returning level instead of level + 1 — the problem counts words in the sequence, not edges. The starting word counts as 1.

Follow-up questions

An interviewer at Juniper Networks may pivot to one of these next:

  • Word Ladder II (LC 126) — return all shortest transformation sequences.
  • How would you find the minimum number of routing hops between two routers in a network topology graph?
  • How does bidirectional BFS relate to bidirectional Dijkstra used in road network shortest-path calculations?

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 (not DFS) the right algorithm here?

BFS explores nodes in level order, guaranteeing that the first time we reach endWord, we have found the shortest path. DFS can find a path but not necessarily the shortest one.

Why generate neighbors by replacing characters rather than building an adjacency list?

Building an explicit adjacency list requires comparing all pairs of words — O(N² * M). The character-substitution approach generates neighbors in O(M * 26) per word, which is faster when N is large.

Why does the problem return word count, not edge count?

The problem includes beginWord in the count. A transformation of 4 edges produces a sequence of 5 words. Initializing level = 1 (for beginWord) handles this correctly.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →