Word Ladder (shortest transformation sequence)

Hard

Problem

Transform beginWord into endWord by changing one letter at a time, where every intermediate word must be in the word list. Return the number of words in the shortest such sequence (including both ends), or 0 if it is impossible.

Example 1

Input:  begin = "hit", end = "cog", list = ["hot","dot","dog","lot","log","cog"]
Output: 5

hit → hot → dot → dog → cog.

Also asked as: word Ladder

Test cases

Case 1

Input:    "hit", "cog", ["hot","dot","dog","lot","log","cog"]
Expected: 5

Case 2

Input:    "hit", "cog", ["hot","dot","dog","lot","log"]
Expected: 0

Case 3

Input:    "a", "c", ["a","b","c"]
Expected: 2

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. BFS over words, neighbours = one-letter changes

Time O(N · L · 26)Space O(N · L)

From each word, generate all words that differ by one letter; keep those in the dictionary. BFS distance from beginWord to endWord + 1 is the ladder length.

function ladderLength(begin, end, wordList) {
const dict = new Set(wordList);
if (!dict.has(end)) return 0;
let q = [begin], steps = 1;
dict.delete(begin);
while (q.length) {
const next = [];
for (const word of q) {
if (word === end) return steps;
for (let i = 0; i < word.length; i++) {
for (let c = 97; c < 123; c++) {
const cand = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
if (dict.has(cand)) { dict.delete(cand); next.push(cand); }
}
}
}
q = next; steps++;
}
return 0;
}