Word bucketing in Python First I'm not sure what this is called formally but whatever.

Basically I need to form "wildcard buckets". I think the best way to explain what I need to do is to take an example. For instance, say I have the three words "aaa", "aab", and "baa".

Let me use * as the wildcard. Then from aaa I can form -aa, a-a, aa-, --a, a--, a-a, and ---. I then add these to a dictionary where the keys are the buckets and values are sets of (complete) words that fit these buckets. I repeat for all my words. So in the end I get that, for instance, -a- fits all three of the example words that I have above.

I have working code, but it is very slow in forming these buckets when I have a word list that has hundreds of thousands of words.

for numberSpaces in range(0, len(word) + 1):  # loop through all spaces of word
    buckets = itertools.combinations(range(0, len(word)), numberSpaces)
    for indicesToReplace in buckets:  # for each index in this combination
        newWord = word  
        for index in indicesToReplace:  # replace character with "*"
            newWord = newWord[0:index] + "*" + newWord[index + 1:]
        if newWord not in bucketDictionary.keys(): # Add to dictionary
            bucketDictionary[newWord] = set()
        bucketDictionary[newWord].add(word)


I would like to know how to best optimize this code. I've tried recursion but I'm not sure if that is any better than this iterative method.

Thank you!
I think the way to optimize it is to try an entirely different approach -- given a pattern that matches all the words in a set, and a new word to add to the set, how do you modify the pattern to match the new word as well?  Simple answer: as long as the non-wild characters in the pattern match the new word, leave them; otherwise change the pattern to have a wildcard at that position.  You could implement this either recursively or iteratively.

from typing import List

WILD = "*"

def build_common_pattern(words: List[str]) -&gt; str:
    """Build a pattern matching all input words.
    WILD matches any single character."""
    pattern = words[0]
    for word in words:
        assert len(word) == len(pattern)
        for i in range(len(word)):
            assert word[i] != WILD
            if pattern[i] != word[i]:
                pattern = pattern[:i] + WILD + pattern[i+1:]
    return pattern

print(build_common_pattern(["aaa", "aab", "baa"]))


This is also a potential use case for functools.reduce:

def build_common_pattern(words: List[str]) -&gt; str:
    """Build a pattern matching all input words.
    WILD matches any single character."""
    def union(a: str, b: str) -&gt; str:
        result = ""
        assert len(a) == len(b)
        for i in range(len(a)):
            result += a[i] if a[i] == b[i] else WILD
        return result

    return reduce(union, words)