Skip to main content

127. Word Ladder

hardAsked at Atlassian

Word Ladder is the canonical Atlassian BFS-on-implicit-graph problem. Given beginWord, endWord, and a dictionary, return the length of the shortest transformation sequence such that each step changes one letter and every intermediate word is in the dictionary. Atlassian uses it to test whether you can identify when BFS is the right tool.

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

Source citations

Public interview reports confirming this problem appears in Atlassian loops.

  • Glassdoor (2026-Q1)— Atlassian Senior onsite reports cite Word Ladder as a recurring graph-BFS problem, often after Number of Islands.
  • Blind (2025-08)— Atlassian L5 interview threads mention Word Ladder including the bidirectional BFS optimization as a Senior-level expectation.

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), and sk == endWord. Given two words and the dictionary, return the number of words in the shortest transformation sequence, 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.

Example 2

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

Approaches

1. BFS with on-the-fly neighbor generation (canonical)

BFS from beginWord. For each word, generate all 1-letter mutations; if a mutation is in the dictionary and unvisited, enqueue it with depth+1.

Time
O(N * L^2) where N = wordList size, L = word length
Space
O(N * L)
function ladderLength(beginWord, endWord, wordList) {
  const dict = new Set(wordList);
  if (!dict.has(endWord)) return 0;
  const visited = new Set([beginWord]);
  let queue = [beginWord];
  let depth = 1;
  while (queue.length) {
    const next = [];
    for (const word of queue) {
      if (word === endWord) return depth;
      const chars = word.split('');
      for (let i = 0; i < chars.length; i++) {
        const original = chars[i];
        for (let c = 97; c <= 122; c++) {
          const ch = String.fromCharCode(c);
          if (ch === original) continue;
          chars[i] = ch;
          const candidate = chars.join('');
          if (dict.has(candidate) && !visited.has(candidate)) {
            visited.add(candidate);
            next.push(candidate);
          }
        }
        chars[i] = original;
      }
    }
    queue = next;
    depth++;
  }
  return 0;
}

Tradeoff: Standard BFS. The N*L^2 factor comes from generating 26*L mutations per word, each costing L to build the string. Acceptable at SWE-II. Mention the alternative pattern-key approach (build buckets keyed on hit -> h*t, *it, hi*) for slight speedup.

2. Bidirectional BFS (Senior+ optimization)

BFS simultaneously from beginWord and endWord, alternating which frontier to expand (smaller first). Meet in the middle ⇒ depth roughly halved at the expense of two sets.

Time
O(N * L^2) worst case but ~sqrt(branching) factor better in practice
Space
O(N * L)
function ladderLengthBidirectional(beginWord, endWord, wordList) {
  const dict = new Set(wordList);
  if (!dict.has(endWord)) return 0;
  let beginSet = new Set([beginWord]);
  let endSet = new Set([endWord]);
  const visited = new Set([beginWord, endWord]);
  let depth = 1;
  while (beginSet.size && endSet.size) {
    if (beginSet.size > endSet.size) {
      const tmp = beginSet;
      beginSet = endSet;
      endSet = tmp;
    }
    const next = new Set();
    for (const word of beginSet) {
      const chars = word.split('');
      for (let i = 0; i < chars.length; i++) {
        const original = chars[i];
        for (let c = 97; c <= 122; c++) {
          const ch = String.fromCharCode(c);
          if (ch === original) continue;
          chars[i] = ch;
          const candidate = chars.join('');
          if (endSet.has(candidate)) return depth + 1;
          if (dict.has(candidate) && !visited.has(candidate)) {
            visited.add(candidate);
            next.add(candidate);
          }
        }
        chars[i] = original;
      }
    }
    beginSet = next;
    depth++;
  }
  return 0;
}

Tradeoff: Same worst-case big-O but typically several times faster because BFS frontier grows exponentially; cutting search depth in half cuts the largest frontier proportionally. Atlassian Senior interviewers explicitly check for this optimization.

Atlassian-specific tips

Atlassian Senior+ rounds explicitly look for bidirectional BFS as the optimization. State out loud 'standard BFS is N*L^2; I can roughly halve the search depth with bidirectional BFS' — even if you don't have time to code both. The interviewer is grading whether you KNOW the optimization exists, not necessarily whether you can write it under time pressure. For SWE-II the on-the-fly mutation version is acceptable on its own.

Common mistakes

  • Checking 'is candidate in dict' inside the inner loop without also removing it from dict — visited check matters.
  • Returning depth instead of depth+1 — the count includes both endpoints (LeetCode's spec).
  • Forgetting the early-out `if (!dict.has(endWord)) return 0` — without it you'll BFS forever on unsolvable inputs.

Follow-up questions

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

  • Word Ladder II (LeetCode 126) — return ALL shortest transformation sequences. Forces parent tracking + DFS reconstruction.
  • What if the dictionary is huge and word length is large (e.g., 100)? Precompute pattern buckets (h*t -> [hat, hit, hot, hut]) so neighbor lookup is O(L) instead of O(L * 26 * L).
  • How would you handle Unicode? Same algorithm but enumerate code points instead of a-z.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Is bidirectional BFS required at Atlassian?

Not for SWE-II. For SWE-III / Senior the rubric treats it as a 'meets expectations' optimization to at least name; coding it is a 'exceeds'. State the idea even if you ship the unidirectional version.

Why is BFS rather than DFS?

BFS naturally returns shortest paths in unweighted graphs; DFS would find some path but not the shortest. The implicit graph here is unweighted (every transformation is 1 step), so BFS is the right tool.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →