Word Ladder

Build the “differs by one letter” graph explicitly: compare every pair of words in {beginWord} ∪ wordList, and connect them if they differ in exactly one position. Then BFS from beginWord to endWord over that graph.

from collections import deque

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: list[str]) -> int:
        if endWord not in wordList:
            return 0

        words = list(dict.fromkeys([beginWord] + wordList))  # dedupe, keep order

        def differs_by_one(a, b):
            return sum(1 for x, y in zip(a, b) if x != y) == 1

        graph = {w: [] for w in words}
        for i in range(len(words)):
            for j in range(i + 1, len(words)):
                if differs_by_one(words[i], words[j]):
                    graph[words[i]].append(words[j])
                    graph[words[j]].append(words[i])

        queue = deque([(beginWord, 1)])
        visited = {beginWord}
        while queue:
            word, dist = queue.popleft()
            if word == endWord:
                return dist
            for neighbor in graph[word]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, dist + 1))
        return 0

Why it’s correct: the graph exactly captures the problem’s adjacency rule (differ by one letter), and BFS from beginWord finds the shortest path to endWord in an unweighted graph by construction. Complexity: comparing every pair of the N words (each of length L) costs O(N² · L) time just to build the graph, and storing every edge found costs up to O(N²) space in the worst case (a dense “differs by one” graph) — this dominates over the BFS itself, which is only O(N + E).

Instead of discovering neighbors by comparing against every other word, generate them directly: for the current word, try replacing each of its L positions with each of the 26 letters, and check whether the result is in the dictionary (a hash set lookup, O(L) to hash). This produces the same neighbors without ever comparing two dictionary words against each other.

from collections import deque

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: list[str]) -> int:
        word_set = set(wordList)
        if endWord not in word_set:
            return 0

        queue = deque([(beginWord, 1)])
        visited = {beginWord}

        while queue:
            word, dist = queue.popleft()
            if word == endWord:
                return dist
            for i in range(len(word)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    if c == word[i]:
                        continue
                    candidate = word[:i] + c + word[i + 1:]
                    if candidate in word_set and candidate not in visited:
                        visited.add(candidate)
                        queue.append((candidate, dist + 1))
        return 0

Trace beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]. Watch the frontier grow one row at a time: each pop tries all 75 letter swaps, and its dictionary survivors slide onto the row directly below — so the row number is the distance, and the shortest chain is the one that first reaches cog.

The emerald chain hit → hot → dot → dog → cog is the shortest transformation sequence: five words, matching the expected output of 5.

Why it’s correct: for a word of length L over a fixed alphabet, generating all L * 25 single-letter variants and checking dictionary membership finds exactly the same neighbor set as an explicit pairwise comparison, just without ever materializing the full edge list; BFS over this implicit graph still explores nodes in order of increasing distance, so the first time endWord is popped, dist is the shortest possible. Complexity: each of the N words is dequeued once, and generating its neighbors costs O(L · 26) → O(N · L · 26) time, which for a bounded alphabet is effectively O(N · L) and much better than O(N² · L) when N is large. Space is O(N · L) for the word set, visited set, and queue holding words of length L.