127. Word Ladder

Problem¶

Find the number of words in the shortest path from beginWord to endWord, changing exactly one letter at a time and using only words from wordList; return 0 if impossible.

begin="hit", end="cog", words=["hot","dot","dog","lot","log","cog"]
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
output=5

Key trick¶

Treat words as an unweighted graph and use bidirectional BFS, generating valid one-letter mutations instead of comparing every pair of words.

Trap¶

Building the entire graph by comparing every pair costs \(O(N^2L)\) and can time out.
The answer counts words, not transformations, so the initial length is 1.
Mark words visited when discovered, not when later processed.
endWord must be in wordList.

Why is it interesting?¶

It combines implicit graph construction, shortest-path BFS, and bidirectional search without materializing an expensive adjacency list.

Python solution¶

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

        # Search from both ends, always expanding the smaller frontier.
        front = {beginWord}
        back = {endWord}
        words.discard(beginWord)
        words.discard(endWord)

        length = 1
        alphabet = "abcdefghijklmnopqrstuvwxyz"

        while front:
            if len(front) > len(back):
                front, back = back, front

            next_front = set()

            for word in front:
                for i, original in enumerate(word):
                    for letter in alphabet:
                        if letter == original:
                            continue

                        cand = word[:i] + letter + word[i + 1:]

                        # The two searches have met.
                        if cand in back:
                            return length + 1

                        if cand in words:
                            # Removing immediately prevents duplicate visits.
                            words.remove(cand)
                            next_front.add(cand)

            front = next_front
            length += 1

        return 0

Comment on my solution¶

Your BFS and visited handling are correct, but constructing all pairwise edges costs \(O(N^2L)\), which causes the timeout.

Also, the import contains a typo: collection should be collections. Generating one-letter mutations during BFS avoids both the adjacency list and pairwise comparisons.

# IDEAS
# - check first if endWord in worldList
# - shortest => bfs
#   - maybe multi bfs starting at every word
# - it feels backtracking
# - keep a best running variable for the shortest path
#   - only needed if we can't find an algo that finds the shortest
#     directly
# - what if we sort wordList firt?
#   - maybe help for the comparison between adjacent words in the path
# - maybe build adjacency list
#   - word -> [word that differ only by one letter]
#   - then we do shortest path in that unweighted graph
#     from beginWord -> endWord

from collections import defaultdict, deque

# WRONG
# Time Limit Exceeded: 46/57 testcases passed
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: list[str]) -> int:
        # beginWord = "hit", endWord = "cog",
        # wordList = ["hot","dot","dog","lot","log","cog"]
        # "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.
        # => 5
        #
        # beginWord = "hit", endWord = "cog",
        # wordList = ["hot","dot","dog","lot","log"]
        # => 0

        if endWord not in wordList:
            return 0

        graph = defaultdict(list)

        def differ_by_one(s1, s2):
            count = 0
            for i in range(len(s1)):
                if s1[i] != s2[i]:
                    count += 1
            return count == 1

        for s in wordList:
            if differ_by_one(beginWord, s):
                graph[beginWord].append(s)

        for s1 in wordList:
            for s2 in wordList:
                if differ_by_one(s1, s2):
                    graph[s1].append(s2)

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

        while queue:
            node, position_in_path = queue.popleft()
            if node == endWord:
                return position_in_path
            for nei in graph[node]:
                if nei not in visited:
                    visited.add(nei)
                    queue.append((nei, position_in_path + 1))

        return 0