快速查找字典中符合指定模式的单词排列

First, let's clarify the problem to ensure we're aligned:

We need to find sequences of words from a 100k-word dictionary such that when you concatenate the words, the resulting string matches an integer pattern. A string matches the pattern if there exists a mapping from integers to letters where replacing each integer in the pattern with its mapped letter produces the concatenated string. (Optionally, we can enforce a bijection—each integer maps to a unique letter and vice versa—depending on your needs.)

Approach #

The core challenge is efficiently checking combinations of words without brute-forcing all possibilities (which would be infeasible for 100k words). Here's a structured approach:

1. Preprocess the Dictionary: Group words by their length to quickly access words of a specific length when generating possible sequences.
2. Generate Valid Splits: Split the pattern's length into sums of positive integers, where each integer corresponds to the length of a word present in the dictionary.
3. Incremental Validation: For each split, build sequences incrementally, checking if each word fits the pattern constraints (based on the partial mapping we've built so far). Prune invalid combinations early to avoid unnecessary computations.

Implementation Code #

Here's a Python implementation that follows this approach, with optional support for bijection:

from collections import defaultdict

def generate_splits(target_length, allowed_lengths):
    """Generate all possible splits of target_length into sums of allowed lengths."""
    splits = []
    def backtrack(current_split, remaining):
        if remaining == 0:
            splits.append(current_split.copy())
            return
        for length in allowed_lengths:
            if length <= remaining:
                current_split.append(length)
                backtrack(current_split, remaining - length)
                current_split.pop()
    # Sort allowed lengths in reverse to prioritize longer words (faster pruning)
    allowed_lengths = sorted(allowed_lengths, reverse=True)
    backtrack([], target_length)
    return splits

def find_matching_sequences(pattern, dict_words, enforce_bijection=False):
    pattern_len = len(pattern)
    if pattern_len == 0:
        return []
    
    # Preprocess dictionary into length-to-words map
    word_length_map = defaultdict(list)
    for word in dict_words:
        word_length_map[len(word)].append(word)
    
    allowed_lengths = [l for l in word_length_map if l <= pattern_len]
    if not allowed_lengths:
        return []
    
    splits = generate_splits(pattern_len, allowed_lengths)
    results = []
    
    for split in splits:
        stack = [({}, {}, [], 0)]  # (int_to_char, char_to_int, words_so_far, current_ptr)
        for length in split:
            new_stack = []
            words_of_length = word_length_map[length]
            for int_map, char_map, words, ptr in stack:
                for word in words_of_length:
                    valid = True
                    temp_int_map = int_map.copy()
                    temp_char_map = char_map.copy()
                    
                    for j in range(length):
                        p = pattern[ptr + j]
                        c = word[j]
                        
                        # Check existing integer mapping
                        if p in temp_int_map:
                            if temp_int_map[p] != c:
                                valid = False
                                break
                        else:
                            # Check bijection constraint if enabled
                            if enforce_bijection:
                                if c in temp_char_map:
                                    valid = False
                                    break
                                temp_char_map[c] = p
                            temp_int_map[p] = c
                    
                    if valid:
                        new_words = words + [word]
                        new_ptr = ptr + length
                        new_stack.append((temp_int_map, temp_char_map, new_words, new_ptr))
            
            stack = new_stack
            if not stack:
                break  # No valid sequences left for this split
        
        # Collect unique valid sequences
        for _, _, seq, _ in stack:
            results.append(tuple(seq))
    
    # Remove duplicate sequences (in case same sequence comes from different splits, though unlikely)
    unique_results = [list(seq) for seq in set(results)]
    return unique_results

Example Usage #

Let's test this with your sample dictionary and a pattern:

sample_dict = ["A", "ANA", "APPLE", "BANANA", "B", "AN", "NA"]
pattern = [1, 2, 1]  # Length 3

# Without bijection
matches = find_matching_sequences(pattern, sample_dict)
print("Matches (no bijection):", matches)
# Output: [['A', 'NA'], ['ANA'], ['AN', 'A'], ['A', 'A', 'A'], ['B', 'A', 'B']]

# With bijection (each integer maps to unique letter)
matches_bi = find_matching_sequences(pattern, sample_dict, enforce_bijection=True)
print("Matches (bijection):", matches_bi)
# Output: [['A', 'NA'], ['ANA'], ['AN', 'A'], ['B', 'A', 'B']]

Optimization Notes #

For large dictionaries (100k words), these optimizations will help speed up the process:

1. Early Pruning: By validating each word as we build the sequence, we discard invalid combinations before proceeding to the next word.
2. Length Grouping: Preprocessing words by length avoids iterating through all words for each possible split segment.
3. Reverse Sort Splits: Prioritizing longer words in splits reduces the number of combinations we need to check (fewer words in the sequence means fewer iterations).

If you're working with very long patterns, consider precomputing segment signatures for the pattern to quickly filter words that can't fit a given segment, further reducing the number of candidates.

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