LeetCode 127: Word Ladder — Step-by-Step Visual Trace

Hard — BFS | Graph | Hash Table | String

The Problem

Find the length of the shortest transformation sequence from beginWord to endWord, where each transformation changes exactly one letter and each intermediate word must exist in the given wordList.

Approach

Use BFS to explore all possible single-character transformations level by level. For each word, try replacing each character with all 26 letters, check if the new word exists in wordSet, and add valid unvisited words to the queue with incremented level count.

Time: O(M² × N) · Space: O(M × N)

Code

from collections import deque

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

        queue = deque([(beginWord, 1)])  # Start from the beginWord with level 1
        visited = set()

        while queue:
            word, level = queue.popleft()
            if word == endWord:
                return level

            for i in range(len(word)):
                for c in "abcdefghijklmnopqrstuvwxyz":
                    new_word = word[:i] + c + word[i + 1 :]
                    if new_word in wordSet and new_word not in visited:
                        visited.add(new_word)
                        queue.append((new_word, level + 1))

        return 0

Watch It Run

Try it yourself: Open TraceLit and step through every line.

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

Comments