# 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()


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]) -> 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]) -> str:
"""Build a pattern matching all input words.
WILD matches any single character."""
def union(a: str, b: str) -> 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)


Starting with the answer by @SamStafford, you could take this even further and make it a nice inheritance exercise by using a sub-class of str that compares true to any other character:

class WildCard(str):
def __eq__(self, other):
# all other strings are equal to the wildcard
return isinstance(other, str)

STAR = WildCard("*")

def build_common_pattern(words):
"""Build a pattern matching all input words.
WILD matches any single character."""
pattern = list(words[0])
for word in words:
assert len(word) == len(pattern)
pattern = [p if c == p else STAR for c, p in zip(word, pattern)]
return "".join(pattern)


This way you avoid having to do many string slices, although this makes it only perform better for really large strings (patterns with each character having a 50% chance to be a wildcard and a length of more than 1k characters):

However, this does not solve the exact problem your code solves, since it does not build a dictionary mapping patterns to words that match it. For this I can only give you some stylistic advice on how to improve your code.

• Python has an official style-guide, PEP8, which recommends lower_case for functions and variables.

• You can use collections.defaultdict(set) to avoid having to check if you have seen a pattern before.

• range starts by default at 0, and so do slices.

• Use the same way I used above to avoid string slices and iterate over the word/pattern instead.

from collections import defaultdict
from itertools import combinations

def build_buckets(words):
buckets_dict = defaultdict(set)
for word in words:
for number_spaces in range(len(word) + 1):  # loop through all spaces of word
buckets = combinations(range(len(word)), number_spaces)
for indices in map(set, buckets):  # for each index in this combination
new_word = "".join(c if i not in indices else "*"
for i, c in enumerate(word))