#149

Word Ladder

hard

hash-tablestringbreadth-first-search

A transformation sequence from beginWord to endWord is a sequence of words begin -> w1 -> w2 -> ... -> end where:

- every adjacent pair of words differs by exactly one letter, - every word after beginWord is present in wordList (beginWord itself need not be), and - all words have the same length.

Given beginWord, endWord, and the dictionary wordList, return the number of words in the shortest such transformation sequence (counting both ends). If no transformation sequence exists, return 0.

Example

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

Output: 5

hit -> hot -> dot -> dog -> cog has 5 words, and no shorter sequence reaches cog.

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, and all words in wordList are unique.

Intuition

A natural first attempt treats the dictionary as a graph — words are nodes, and an edge joins two words that differ in exactly one letter — then explores every transformation path from beginWord to endWord with DFS/backtracking, remembering the shortest path length seen so far.

function ladderLength(beginWord, endWord, wordList) {
  const dict = new Set(wordList);
  if (!dict.has(endWord)) return 0;        // endWord can never be reached if it isn't in the dictionary

  let shortest = Infinity;
  // Explore every transformation path out of `word`, tracking words already used on *this* path.
  const dfs = (word, visited, length) => {
    if (word === endWord) {
      shortest = Math.min(shortest, length);  // record this path's length, keep looking for a shorter one
      return;
    }
    // Try every one-letter substitution of the current word.
    for (let i = 0; i < word.length; i++) {
      for (let code = 97; code < 97 + 26; code++) {
        const candidate = word.slice(0, i) + String.fromCharCode(code) + word.slice(i + 1);
        if (dict.has(candidate) && !visited.has(candidate)) {
          visited.add(candidate);            // claim it for this path only
          dfs(candidate, visited, length + 1);
          visited.delete(candidate);         // backtrack so a different path can still use it
        }
      }
    }
  };

  dfs(beginWord, new Set([beginWord]), 1);
  return shortest === Infinity ? 0 : shortest;
}

Brute force — DFS/backtracking over every transformation path, keeping the shortest: exponential — up to O((26L)^N) in the worst case, from re-exploring the same words down different paths.

This DFS is correct but wasteful: the same word can be reached from many different partial paths, and because visited is undone on backtrack rather than remembered globally, every one of those paths re-explores it as if for the first time. Can we do better?

The key observation: we don't need every path, only the length of the shortest one — and in an unweighted graph, BFS finds shortest paths for free by expanding outward one edge at a time. The first time BFS reaches a word, it does so along a shortest route to it, so no later path can ever improve on that word's distance — each word only needs to be visited once, ever. The stored solution bakes that in directly: the moment a candidate word is found in the dictionary it's deleted from it, so it can never be rediscovered and re-enqueued by a different branch.

A word graph has no faithful lane, grid, or list animation — it's neither a fixed sequence nor a board nor a chain, so a static picture of the graph, read level by level, teaches the mechanic honestly where a forced lane would not. Walking it through with the hit -> cog example (wordList = [hot, dot, dog, lot, log, cog]):

BFS grows outward from hit one edge at a time. Frontier 1: hot. Frontier 2: dot and lot (hot's one-letter neighbours — both removed from the dictionary the instant they're discovered). Frontier 3: dog (from dot) and log (from lot); dot's other neighbour, lot, is skipped because it was already claimed the moment hot was expanded, the very step that discovered dot itself. Frontier 4: cog, reached from either dog or log — the target. BFS returns 5 words counting hit itself: hit → hot → dot → dog → cog is one shortest route, hit → hot → lot → log → cog is another, both length 5.

Optimization

BFS over the word graph

Picture each word as a node, with an edge between two words that differ by exactly one letter. The shortest transformation sequence is then the shortest path from beginWord to endWord in that graph — and BFS finds shortest paths in an unweighted graph.

Put the dictionary in a set for O(1) membership. BFS level by level from beginWord; to find a word's neighbours, try every single-letter substitution (each of its positions × 26 letters) and keep those still in the set, removing each from the set as you enqueue it so no word is visited twice. The level number when endWord is dequeued is the answer (sequence length = levels including the start). If the queue empties without reaching endWord, return 0.

O(N · L² · 26) in the worst case for N words of length L (each word generates L · 26 candidates, each costing O(L) to build), and O(N · L) space for the set and queue.

function ladderLength(beginWord, endWord, wordList) {
  const dict = new Set(wordList);
  if (!dict.has(endWord)) return 0;        // can never finish on a word not in the list

  let queue = [beginWord];
  let length = 1;                          // beginWord itself is the first word in the sequence
  const a = "a".charCodeAt(0);

  while (queue.length > 0) {
    const next = [];
    for (const word of queue) {
      if (word === endWord) return length; // reached the target at this level
      // Generate every one-letter variation of this word.
      for (let i = 0; i < word.length; i++) {
        for (let k = 0; k < 26; k++) {
          const candidate = word.slice(0, i) + String.fromCharCode(a + k) + word.slice(i + 1);
          if (dict.has(candidate)) {
            dict.delete(candidate);        // claim it so it isn't revisited
            next.push(candidate);
          }
        }
      }
    }
    queue = next;
    length++;                              // advanced one level deeper
  }
  return 0;                                // endWord never reached
}

Complexity analysis

Time complexity: O(N · L² · 26), where N is the number of words in the dictionary and L is the word length. Here's why:

Each word is enqueued at most once — it's deleted from the dictionary the moment it's claimed, so BFS processes at most N words in total.
For each word, generating every one-letter variant tries L positions × 26 letters, and building each O(L)-length candidate string costs O(L).

So the total work is N words × O(L · 26) candidates × O(L) per candidate, giving O(N · L² · 26).

Space complexity: O(N · L). Here's why:

The dictionary set holds up to N words of length L.
The BFS queue holds at most one frontier's worth of words, also bounded by N.

Both are dominated by the dictionary, so the extra space is O(N · L) — the output is a single number, not counted separately.

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
beginWord = "hit", endWord = "cog", wordList = []	0	Empty dictionary — endWord can never appear, so BFS never even starts.
beginWord = "cat", endWord = "cot", wordList = ["cot"]	2	beginWord is one hop from endWord — the shortest ladder is just the two words.
beginWord = "cat", endWord = "dog", wordList = ["dot","dog"]	0	dog is in the dictionary but unreachable — cat and dot differ in two letters, so no ladder connects them.
beginWord = "a", endWord = "d", wordList = ["a","b","c","d"]	2	Single-letter words are all pairwise one substitution apart, so beginWord jumps straight to endWord.
beginWord = "dog", endWord = "cat", wordList = ["dot","dat","cat"]	4	Each hop changes a different letter position, forcing BFS to route through two intermediaries.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor