单词接龙算法优化：LeetCode题解超时的时间复杂度优化问询

Hey there! Let's break down why your code is timing out on big test cases and how to fix it. Your current approach works for small inputs, but the way you build the graph and run BFS isn't efficient enough for large word lists. Here's the breakdown and actionable fixes:

What's Causing the Timeout? #

Your code builds the adjacency list by checking every pair of words to see if they differ by one character. That's an O(n²) operation—if you have 10,000 words, that's 100 million comparisons! No wonder it's slow on large datasets. Plus, single-direction BFS can end up traversing way more nodes than necessary when the shortest path is long.

Key Optimizations #

1. Build the Graph Efficiently with "Generic States" #

Instead of comparing every pair of words, we can create a map where each key is a "generic" version of a word (replace one character with a wildcard like *), and the value is all words that match that pattern. For example, "hot" would map to *ot, h*t, and ho*—any word sharing one of these patterns is a valid neighbor. This cuts graph-building time to O(n*L) (L is word length), which is way better than O(n²).

2. Use Bidirectional BFS #

Instead of starting only from the beginWord, run BFS from both the beginWord and endWord at the same time. When the two search fronts meet, you've found the shortest path. This reduces the number of nodes you need to visit—instead of exploring b^d nodes (b = average neighbors per word, d = path length), you explore 2*b^(d/2) nodes, a huge saving for longer paths.

Optimized Code Implementation #

from collections import defaultdict, deque

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: list[str]) -> int:
        # Edge case: if endWord isn't in the word list, return 0 immediately
        word_set = set(wordList)
        if endWord not in word_set:
            return 0
        
        # Preprocess: build map of generic states to matching words
        generic_map = defaultdict(list)
        word_length = len(beginWord)
        # Include beginWord in our processing
        all_words = word_set | {beginWord}
        
        for word in all_words:
            for i in range(word_length):
                # Create generic pattern (replace i-th character with *)
                generic_pattern = word[:i] + "*" + word[i+1:]
                generic_map[generic_pattern].append(word)
        
        # Bidirectional BFS setup
        forward_queue = deque([(beginWord, 1)])
        forward_seen = {beginWord: 1}
        
        backward_queue = deque([(endWord, 1)])
        backward_seen = {endWord: 1}
        
        while forward_queue and backward_queue:
            # Process forward direction
            current_word, steps = forward_queue.popleft()
            for i in range(word_length):
                pattern = current_word[:i] + "*" + current_word[i+1:]
                for neighbor in generic_map.get(pattern, []):
                    if neighbor in backward_seen:
                        # Path found: sum steps from both directions
                        return steps + backward_seen[neighbor]
                    if neighbor not in forward_seen:
                        forward_seen[neighbor] = steps + 1
                        forward_queue.append((neighbor, steps + 1))
                # Delete processed pattern to avoid rework
                if pattern in generic_map:
                    del generic_map[pattern]
            
            # Process backward direction
            current_word, steps = backward_queue.popleft()
            for i in range(word_length):
                pattern = current_word[:i] + "*" + current_word[i+1:]
                for neighbor in generic_map.get(pattern, []):
                    if neighbor in forward_seen:
                        return forward_seen[neighbor] + steps
                    if neighbor not in backward_seen:
                        backward_seen[neighbor] = steps + 1
                        backward_queue.append((neighbor, steps + 1))
                if pattern in generic_map:
                    del generic_map[pattern]
        
        # No valid path exists
        return 0

Quick Notes on the Optimized Code #

• We first check if endWord is in the word list to avoid wasted work.
• Deleting processed generic patterns prevents us from reprocessing the same neighbors multiple times, which adds another layer of efficiency.
• Bidirectional BFS drastically cuts the search space, making it feasible for large test cases.

内容的提问来源于stack exchange，提问作者nz_21