leetcode-127 Word Ladder

# A transformation sequence from word beginWord to word endWord using a dictionary
# wordList is a sequence of words such that:
# - The first word is beginWord.
# - The last word is endWord.
# - Only one letter is different between each adjacent pair.
# - Every word in the sequence is in wordList.
# Return the length of the shortest transformation sequence, or 0 if none exists.
#
# Example 1:
# Input: beginWord = "hit", endWord = "cog",
#        wordList = ["hot","dot","dog","lot","log","cog"]
# Output: 5
# Explanation: "hit" -> "hot" -> "dot" -> "dog" -> "cog"
#
# Example 2:
# Input: beginWord = "hit", endWord = "cog",
#        wordList = ["hot","dot","dog","lot","log"]
# Output: 0
#
# Constraints:
# 1 <= beginWord.length <= 10
# endWord.length == beginWord.length
# 1 <= wordList.length <= 5000

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: "*ot" -> ["hot", "dot", "lot"]
        word_set = set(wordList)
        patterns = defaultdict(list)

        for word in wordList:
            for i in range(len(word)):
                pattern = word[:i] + '*' + word[i+1:]
                patterns[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 of current word
            for i in range(len(word)):
                pattern = word[:i] + '*' + word[i+1:]

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

        return 0

    # Approach 2: Bidirectional BFS (faster)
    def ladderLength2(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList:
            return 0

        word_set = set(wordList)
        if beginWord in word_set:
            word_set.remove(beginWord)

        # BFS from both ends
        begin_set = {beginWord}
        end_set = {endWord}
        length = 1

        while begin_set and end_set:
            # Always expand the smaller set
            if len(begin_set) > len(end_set):
                begin_set, end_set = end_set, begin_set

            next_set = set()
            for word in begin_set:
                # Try changing each character
                for i in range(len(word)):
                    for c in 'abcdefghijklmnopqrstuvwxyz':
                        next_word = word[:i] + c + word[i+1:]

                        if next_word in end_set:
                            return length + 1

                        if next_word in word_set:
                            next_set.add(next_word)
                            word_set.remove(next_word)

            begin_set = next_set
            length += 1

        return 0

# BFS: Time O(M^2 * N), Space O(M^2 * N)
#   M = word length, N = number of words
# Bidirectional BFS: Time O(M^2 * N), Space O(M^2 * N)
#   but faster in practice
#
# Why BFS?
# - Need shortest path
# - All edges have equal weight (one letter change)
# - BFS guarantees shortest path in unweighted graph
#
# Pattern Dictionary Optimization:
# Instead of comparing each word with all others (O(N^2 * M))
# Use patterns to group similar words (O(M * N))
#
# AirBnB: Common problem, tests BFS and optimization