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
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.
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
}Try it yourself
Write your solution against the real judge before checking the reference.