Subhra Jyoti Baroieditorial
Chat with me
← Daily Logs
LeetCode 127

Word Ladder

HardJul 24, 2026graphbfsshortest-pathimplicit-graph

The `[node, distance]` queue from `shortestPath` carried over unchanged, but there's no edge list to build a graph from first — the graph is implicit, so a neighbour is discovered by trying every letter at every position and checking a `Set` of the remaining words instead of looking up a precomputed adjacency list.

The problem

Given `beginWord`, `endWord`, and `wordList`, return the number of words in the shortest transformation sequence from `beginWord` to `endWord`, changing exactly one letter per step and landing on a word in `wordList` at every step, or `0` if no such sequence exists.

`beginWord = "cat", endWord = "sag", wordList = ["bat","bag","sag","dag","dot"]` returns `4`: `cat -> bat -> bag -> sag`. If `"sag"` weren't in `wordList` at all, the answer would be `0` regardless of what else the list contained — `endWord` itself has to be reachable, i.e. present in the list.

The approach

There's no `edges` array to turn into a graph here — the adjacency is implicit in the alphabet. So instead of indexing into a precomputed adjacency list like every earlier BFS in this log, a neighbour of `word` is generated on the fly: for each of its positions, swap in each of the 26 letters and check whether the result is a real word still left in a `Set` built from `wordList`.

That `Set` doubles as both the dictionary and the `visited` structure `shortestPath`/`hasPath` used a separate `Set` for — a candidate gets `delete`d the moment it's queued, so it can never be regenerated as a neighbour of some other word later, and there's no second lookup needed to tell 'is this a real word' from 'have I already used this word'.

The queue is exactly `shortestPath`'s `[node, distanceFromSource]` tuple, renamed to `[word, length]` and seeded at `1` instead of `0` — this problem counts *words* in the sequence, not *edges* between them, so `beginWord` itself is the first word already, and the early-return shape (check the candidate against `endWord` before deleting/pushing, return immediately) carries over untouched.

The solution

js
class Solution {
    /**
     * @param {string} beginWord
     * @param {string} endWord
     * @param {string[]} wordList
     * @return {number}
     */
    ladderLength(beginWord, endWord, wordList) {
        const wordSet = new Set(wordList);
        if (!wordSet.has(endWord)) return 0;

        wordSet.delete(beginWord);
        const q = [[beginWord, 1]];

        while (q.length) {
            const [word, length] = q.shift();
            for (let i = 0; i < word.length; i++) {
                for (let code = 97; code <= 122; code++) {
                    const candidate = word.slice(0, i) + String.fromCharCode(code) + word.slice(i + 1);
                    if (wordSet.has(candidate)) {
                        if (candidate === endWord) return length + 1;
                        wordSet.delete(candidate);
                        q.push([candidate, length + 1]);
                    }
                }
            }
        }

        return 0;
    }
}

Time O(n * L^2)Space O(n * L)

All entries