Scrabble算法优化：给定字母生成可构词列表及最优词求解问题

Hey there! Let's break down how to solve your problem—generating all valid words from your input letters and picking the best Scrabble word—using your existing dictionary file.

Your initial idea of using Counter is spot-on, but we can optimize things to handle large dictionaries smoothly. The key is to preprocess your dictionary once (instead of reloading it every time) and then quickly check which words can be formed from your input letters.

First: Preprocess the Dictionary #

We'll load the dictionary and store each word along with its letter count (as a Counter). For even better performance, we can group words by their length so we only check words that are shorter than or equal to your input letter count.

from collections import Counter
import string

# Preprocess dictionary: group words by length and store their letter counts
def load_dictionary(dict_path):
    word_groups = {}
    with open(dict_path, 'r') as f:
        for line in f:
            word = line.strip().lower()
            # Skip words with non-alphabet characters (adjust if your dictionary has exceptions)
            if all(char in string.ascii_lowercase for char in word):
                word_length = len(word)
                if word_length not in word_groups:
                    word_groups[word_length] = []
                word_groups[word_length].append((word, Counter(word)))
    return word_groups

# Load the dictionary once (do this outside your function to avoid repeated file reads)
DICTIONARY = load_dictionary("your_dictionary_file.txt")

Second: Generate All Possible Words #

Now, we'll compare your input letters' count against each eligible word in the preprocessed dictionary to see if it can be formed.

def get_possible_words(input_letters: str):
    input_lower = input_letters.lower()
    input_counter = Counter(input_lower)
    input_length = len(input_lower)
    possible_words = []

    # Only check words that are shorter than or equal to the input letter count
    for word_len in range(1, input_length + 1):
        if word_len not in DICTIONARY:
            continue
        # Check each word in the length group
        for word, word_counter in DICTIONARY[word_len]:
            # Verify every letter in the word is available in sufficient quantity
            if all(input_counter[char] >= count for char, count in word_counter.items()):
                possible_words.append(word)
    return possible_words

For your example input 'car', this will return all valid words like ['a', 'c', 'r', 'ac', 'ar', 'ca', 'cr', 'ra', 'rc', 'car', 'arc'] (assuming those words exist in your dictionary).

Once we have all possible words, we just need to calculate their Scrabble scores and pick the highest-scoring one. We'll use the official Scrabble letter values for accuracy.

def find_optimal(bunch_of_letters: str):
    possible_words = get_possible_words(bunch_of_letters)
    if not possible_words:
        return None  # Or return an empty list if you prefer

    # Official Scrabble letter scores
    SCRABBLE_VALUES = {
        'a': 1, 'b': 3, 'c': 3, 'd': 2, 'e': 1, 'f': 4, 'g': 2,
        'h': 4, 'i': 1, 'j': 8, 'k': 5, 'l': 1, 'm': 3, 'n': 1,
        'o': 1, 'p': 3, 'q': 10, 'r': 1, 's': 1, 't': 1, 'u': 1,
        'v': 4, 'w': 4, 'x': 8, 'y': 4, 'z': 10
    }

    # Calculate score for a single word
    def calculate_scrabble_score(word):
        return sum(SCRABBLE_VALUES[char] for char in word.lower())

    # Sort words by score (descending), then by length (descending) for ties
    possible_words.sort(key=lambda x: (-calculate_scrabble_score(x), -len(x)))

    # Return the top-scoring word (or the full sorted list if you want options)
    return possible_words[0]

Key Notes: #

• Case Insensitivity: We convert everything to lowercase to avoid mismatches between your input and the dictionary.
• Performance: Grouping words by length cuts down on unnecessary checks—we never waste time looking at words longer than your input letters.
• Tiebreaker: If two words have the same score, we prioritize longer words (they're often more valuable in Scrabble and use more of your letters).

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