Word Ladder — Editorial

Opening the reading…

Intuitionwhy shortest word changes are a graph distance

Treat every valid word as a vertex. Connect two vertices when their words differ at exactly one position. A transformation sequence is then a path through this graph, and its length is the number of vertices visited, including beginWord and endWord. Because every allowed change costs one step, the shortest sequence is the shortest path in an unweighted graph.

You do not need to build all graph edges explicitly. From a current word, change each of its L positions to each of the other 25 letters, and check whether the resulting word is still in the dictionary. BFS explores these generated neighbors in increasing distance order, so the first time you reach endWord, no later path can use fewer words.

BFS layers represent the number of words in the sequence.

Approachgenerate only the neighbors the current word can actually have

Put every dictionary word into an unordered set, because membership and removal must be fast; scanning the entire list for every mutation would add an unnecessary factor of the dictionary size.

Return 0 immediately if endWord is absent, because every word after beginWord, including the target, must come from wordList.

Start a queue with beginWord at distance 1, because the answer counts words rather than edges and the starting word is already the first word.

Remove a word from the dictionary as soon as you enqueue it, because marking it only when dequeued lets several parents enqueue the same word and creates duplicate work.

Pop words in queue order and try every replacement letter at every position, restoring the original character after each position; this enumerates exactly the words that differ by one letter without permanently corrupting the current word.

When a generated word remains in the dictionary, remove it, enqueue it with distance d + 1, and let the early target check return its shortest distance; BFS guarantees all distance d words leave the queue before any distance d + 1 word.

If the queue empties without reaching endWord, return 0, because every reachable dictionary word has then been explored and no valid path remains.

Complexitythe dictionary is the graph, even though its edges stay implicit

MEASURE	BOUND	WHY
Time	O(N x L x 26)	Each dictionary word is enqueued at most once. When it is removed from the queue, the algorithm tests 26 replacements at each of its L positions, so the total number of generated candidates is bounded by N x L x 26; hash-set operations are O(1) on average.
Space	O(N x L) extra	The dictionary stores up to N words and the queue can hold up to N words, each of length L. The returned integer uses no output storage; the extra memory is therefore proportional to the stored word characters, and this bound is already reached when many dictionary words are queued or retained.

Here N is the number of words in wordList, L is the common word length, and 26 is the size of the lowercase English alphabet.

Annotated solutionC++ · implicit graph BFS · distances count words

CPPBFS over generated one-letter mutations, with distance initialized to one for beginWord.

#include <string>
#include <unordered_set>
#include <utility>
#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dict(wordList.begin(), wordList.end());
        if (!dict.count(endWord)) return 0;

        queue<pair<string, int>> q;
        q.push({beginWord, 1});
        dict.erase(beginWord);

        while (!q.empty()) {
            auto [word, distance] = q.front();
            q.pop();

            if (word == endWord) return distance;

            string candidate = word;
            for (int i = 0; i < static_cast<int>(candidate.size()); ++i) {
                char original = candidate[i];

                for (char replacement = 'a'; replacement <= 'z'; ++replacement) {
                    if (replacement == original) continue;

                    candidate[i] = replacement;
                    if (dict.count(candidate)) {
                        dict.erase(candidate);
                        q.push({candidate, distance + 1});
                    }
                }

                candidate[i] = original;
            }
        }

        return 0;
    }
};

The candidate string is a reusable copy of the word currently being explored. Each inner loop changes one position, and the restoration after that loop is essential: without it, changing the next position would build mutations from an already modified word rather than from the original word. The dictionary removal is also part of the BFS invariant, not just a performance detail.

Bidirectional BFS reduces the explored searchan optimisation when the search space branches widely

A second reasonable solution searches outward from both beginWord and endWord. Expand the smaller frontier, generate its one-letter mutations, and stop when a generated word already belongs to the opposite frontier. The two searches meet near the middle, which can greatly reduce the number of explored words when the graph branches heavily.

CPPBidirectional BFS expands the smaller frontier and returns when the two searches meet.

#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dictionary(wordList.begin(), wordList.end());
        if (!dictionary.count(endWord)) return 0;

        unordered_set<string> front{beginWord};
        unordered_set<string> back{endWord};
        dictionary.erase(beginWord);
        dictionary.erase(endWord);

        int words = 2;
        while (!front.empty() && !back.empty()) {
            if (front.size() > back.size()) {
                swap(front, back);
            }

            unordered_set<string> next;
            for (const string& word : front) {
                string candidate = word;
                for (int i = 0; i < static_cast<int>(candidate.size()); ++i) {
                    char original = candidate[i];
                    for (char replacement = 'a'; replacement <= 'z'; ++replacement) {
                        if (replacement == original) continue;
                        candidate[i] = replacement;

                        if (back.count(candidate)) return words;
                        if (dictionary.count(candidate)) {
                            dictionary.erase(candidate);
                            next.insert(candidate);
                        }
                    }
                    candidate[i] = original;
                }
            }

            front = move(next);
            ++words;
        }

        return 0;
    }
};

This is an optimisation, not a different answer: both methods use the same implicit neighbors and preserve shortest-path order. The one-sided version has a simpler distance invariant and is usually easier to verify. Bidirectional BFS buys fewer explored layers, but it costs two frontiers and more careful bookkeeping when combining the distances.