Skip to main content

100. Word Ladder

hardAsked at Salesforce

Find the shortest transformation sequence from beginWord to endWord changing one letter at a time. Salesforce uses this as a BFS-on-implicit-graph stress test.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses BFS on implicit graphs in their approval-chain pathfinding.
  • Blind (2025-11)— Salesforce L5+ stretch question.

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 (note that 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

Example 2

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

Approaches

1. BFS with all-pairs check

For each BFS step, scan all words to find unvisited neighbors.

Time
O(n^2 * L)
Space
O(n)
// Slow due to all-pairs comparison.

Tradeoff: TLE on big inputs.

2. BFS with pattern-based adjacency

Build a map pattern -> words sharing that pattern (with one letter wildcarded). BFS pops a word, generates all patterns, visits neighbors via the map.

Time
O(n * L^2)
Space
O(n * L^2)
function ladderLength(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;
  const patterns = new Map();
  for (const word of wordList) {
    for (let i = 0; i < word.length; i++) {
      const p = word.slice(0, i) + '*' + word.slice(i + 1);
      if (!patterns.has(p)) patterns.set(p, []);
      patterns.get(p).push(word);
    }
  }
  const visited = new Set([beginWord]);
  let queue = [[beginWord, 1]];
  while (queue.length) {
    const next = [];
    for (const [word, dist] of queue) {
      if (word === endWord) return dist;
      for (let i = 0; i < word.length; i++) {
        const p = word.slice(0, i) + '*' + word.slice(i + 1);
        for (const nbr of patterns.get(p) || []) {
          if (!visited.has(nbr)) { visited.add(nbr); next.push([nbr, dist + 1]); }
        }
      }
    }
    queue = next;
  }
  return 0;
}

Tradeoff: O(n * L^2). The pattern-map makes neighbor lookup O(L) instead of O(n). Salesforce's preferred answer.

Salesforce-specific tips

Salesforce uses BFS on implicit graphs in their approval-chain pathfinding (find shortest approval path between two roles). They grade on the pattern-based adjacency trick — generating wildcard patterns to look up neighbors in O(L) instead of O(n). Bonus signal: discuss bidirectional BFS as a further optimization — searches from both ends, meeting in the middle.

Common mistakes

  • Comparing every pair of words for adjacency — O(n^2 * L).
  • Marking words visited only AFTER popping — multiple insertions of the same word slow things down.
  • Forgetting to return 0 when endWord isn't in wordList.

Follow-up questions

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

  • Word Ladder II (LC 126) — return all shortest sequences.
  • Open the Lock (LC 752) — same BFS pattern.
  • Minimum Genetic Mutation (LC 433).

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 pattern-based adjacency?

Naive 'check all pairs for one-letter diff' is O(n^2 * L). Patterns reduce neighbor lookup to O(L) by precomputing edges.

Why bidirectional BFS?

Search from both beginWord and endWord. Meets in the middle, exponentially reducing the search space (2 * b^(d/2) vs b^d).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →