24 Apr 2025•Python•Hard

Word Ladder

find shortest transformation sequence from beginWord to endWord using bfs.

use bfs to find shortest path. start from beginWord, try changing each character to all possible letters, check if result is in word list and not visited.

use queue for level-order traversal. track level to count transformations. early return when endWord is found.

optimization

convert word list to set for O(1) lookup. try all 26 letters for each position. use visited set to avoid cycles.

complexity

O(m * n * 26) time where m is word length and n is word list size. O(n) space for queue and visited set.

Solution files

Python•word-ladder/solution.py

from collections import deque

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        if endWord not in wordList:
            return class="syntax-number">0

        wordSet = set(wordList)
        queue = deque([(beginWord, class="syntax-number">1)])

        while queue:
            current_word, steps = queue.popleft()
            if current_word == endWord:
                return steps

            for i in range(len(current_word)):
                for char in class="syntax-string">'abcdefghijklmnopqrstuvwxyz':
                    next_word = current_word[:i] + char + current_word[i+class="syntax-number">1:]
                    if next_word in wordSet:
                        queue.append((next_word, steps + class="syntax-number">1))
                        wordSet.remove(next_word)

        return class="syntax-number">0

solution = Solution()
beginWord = class="syntax-string">"hit"
endWord = class="syntax-string">"cog"
wordList = [class="syntax-string">"hot", class="syntax-string">"dot", class="syntax-string">"dog", class="syntax-string">"lot", class="syntax-string">"log", class="syntax-string">"cog"]

print(solution.ladderLength(beginWord, endWord, wordList))