View on NeetCode
View on LeetCode

Problem

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

• Every adjacent pair of words differs by a single letter.
• Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
• sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> "cog", which is 5 words long.

Example 2:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.

Constraints:

• 1 <= beginWord.length <= 10
• endWord.length == beginWord.length
• 1 <= wordList.length <= 5000
• wordList[i].length == beginWord.length
• beginWord, endWord, and wordList[i] consist of lowercase English letters.
• beginWord != endWord
• All the words in wordList are unique.

Solution

Approach: BFS with Pattern Matching

The key insight is to treat this as a shortest path problem in an unweighted graph where words are nodes and edges connect words differing by one letter.

Implementation

from collections import deque, defaultdict

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

        # Build pattern dictionary
        # For example: "hot" -> ["*ot", "h*t", "ho*"]
        pattern_dict = defaultdict(list)
        wordList.append(beginWord)

        for word in wordList:
            for i in range(len(word)):
                pattern = word[:i] + "*" + word[i+1:]
                pattern_dict[pattern].append(word)

        # BFS
        queue = deque([(beginWord, 1)])  # (word, level)
        visited = {beginWord}

        while queue:
            word, level = queue.popleft()

            if word == endWord:
                return level

            # Try all patterns for current word
            for i in range(len(word)):
                pattern = word[:i] + "*" + word[i+1:]

                # Get all words matching this pattern
                for next_word in pattern_dict[pattern]:
                    if next_word not in visited:
                        visited.add(next_word)
                        queue.append((next_word, level + 1))

        return 0

Approach 2: Bidirectional BFS (Optimized)

from collections import deque, defaultdict

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

        # Build pattern dictionary
        pattern_dict = defaultdict(list)
        wordList.append(beginWord)

        for word in wordList:
            for i in range(len(word)):
                pattern = word[:i] + "*" + word[i+1:]
                pattern_dict[pattern].append(word)

        # Bidirectional BFS
        visited_begin = {beginWord: 1}
        visited_end = {endWord: 1}
        queue_begin = deque([(beginWord, 1)])
        queue_end = deque([(endWord, 1)])

        def visit_neighbors(queue, visited, other_visited):
            word, level = queue.popleft()

            for i in range(len(word)):
                pattern = word[:i] + "*" + word[i+1:]

                for next_word in pattern_dict[pattern]:
                    if next_word in other_visited:
                        return level + other_visited[next_word]

                    if next_word not in visited:
                        visited[next_word] = level + 1
                        queue.append((next_word, level + 1))

            return None

        while queue_begin and queue_end:
            # Search from the smaller queue
            if len(queue_begin) <= len(queue_end):
                result = visit_neighbors(queue_begin, visited_begin, visited_end)
            else:
                result = visit_neighbors(queue_end, visited_end, visited_begin)

            if result:
                return result

        return 0

Complexity Analysis

Standard BFS:

• Time Complexity: O(M² * N), where M is word length and N is wordList size. For each word, we generate M patterns and check neighbors.
• Space Complexity: O(M² * N) for pattern dictionary and visited set.

Bidirectional BFS:

• Time Complexity: O(M² * N), but typically faster in practice as search spaces meet in the middle.
• Space Complexity: O(M² * N).

Key Insights

1. Graph Representation: Words are nodes, edges connect words differing by one letter. We need shortest path, so BFS is natural.

2. Pattern Matching: Instead of comparing every word pair (expensive), we use intermediate patterns like “*ot” to efficiently find neighbors.

3. Preprocessing: Building the pattern dictionary upfront allows O(1) neighbor lookup during BFS.

4. Level Tracking: We track levels/distances to return the length of the transformation sequence.

5. Bidirectional Optimization: Searching from both ends and meeting in the middle can significantly reduce search space.

6. Early Termination: Return immediately when we reach endWord, as BFS guarantees shortest path.