Word Ladder (shortest transformation sequence)
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
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;}