如何高效从英文词典文本文件中匹配目标字母集合的单词？

Got it—generating all permutations is a total dead end for longer inputs, since the number of permutations blows up factorialy, which is completely unsustainable. Let’s break down a way smarter approach that works efficiently even for huge dictionaries and longer input strings.

Core Problem Clarification #

From your examples, you need words where every letter in the word (including its frequency) is fully covered by the input letter set. The input can have extra letters, but the word can’t require any letters the input doesn’t have, or more copies of a letter than the input provides.

Step 1: Preprocess Your Dictionary (One-Time Setup) #

To make lookups fast, we’ll precompute a frequency signature for every word in your dictionary. This signature is a fixed-size tuple counting how many times each letter (a-z) appears in the word. For example:

• "apple" → (1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0) (indexes 0-25 map to a-z)
• "banana" → (3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)

Store these signatures alongside their words. For simplicity, a list of (signature, word) pairs works great—though you can group anagrams together in a dictionary if you want extra functionality.

Step 2: Process the Input #

Take your input string (like "applej") and compute its frequency signature using the same method as above. For "applej", the signature would be (1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1) (note the final 1 for the 'j').

Step 3: Efficiently Match Words #

Now, iterate through your preprocessed dictionary to find matches. Use two quick checks to optimize:

1. Skip longer words first: Any word longer than the input string can be immediately discarded—you can’t make a longer word from fewer letters.
2. Compare signatures: For remaining words, verify that every letter count in the word’s signature is ≤ the corresponding count in the input’s signature. Since each signature is a fixed 26-element tuple, this comparison is O(1) per word.

Example Python Implementation #

from collections import Counter

def preprocess_dictionary(dictionary_path):
    word_signatures = []
    with open(dictionary_path, 'r') as f:
        for line in f:
            word = line.strip().lower()
            # Build frequency signature for the word
            char_count = Counter(word)
            signature = tuple(char_count.get(chr(ord('a') + i), 0) for i in range(26))
            word_signatures.append((signature, word))
    return word_signatures

def find_matching_words(input_str, word_signatures):
    input_count = Counter(input_str.lower())
    input_signature = tuple(input_count.get(chr(ord('a') + i), 0) for i in range(26))
    input_length = len(input_str)
    matches = []
    
    for sig, word in word_signatures:
        # Fast filter: skip words longer than input
        if len(word) > input_length:
            continue
        # Check if word's letter counts are all covered by input
        is_match = all(word_cnt <= input_cnt for word_cnt, input_cnt in zip(sig, input_signature))
        if is_match:
            matches.append(word)
    return matches

# Usage example
dictionary = preprocess_dictionary('your_dictionary.txt')
print(find_matching_words('aplep', dictionary))  # Returns ['apple'] (and other matches if any)
print(find_matching_words('applej', dictionary)) # Also returns ['apple']

Bonus Optimizations for Huge Dictionaries #

If your dictionary has millions of words, these tweaks will speed things up even more:

• Group by word length: Pre-sort your word_signatures into a dictionary where keys are word lengths, and values are lists of (signature, word) pairs. When querying, only check the groups with lengths ≤ input length.
• Precompute letter presence masks: For a quick first pass, you can store a bitmask for each word (where each bit represents whether a letter is present). If the input’s mask doesn’t include all bits set in the word’s mask, you can skip it immediately.

Why This Crushes Permutations #

Generating permutations is O(n!) for an input of length n—completely infeasible for n ≥ 10 (10! = 3.6 million, 15! = 1.3 billion). This approach is O(M) for preprocessing (M = number of dictionary words) and O(K) per lookup (K = number of words ≤ input length), which is totally manageable even for massive dictionaries.

内容的提问来源于stack exchange，提问作者S.Haviv