Summer of Tech Hackfest - Code Challenge (Four letters in common)

four_letters_in_common.py

def get_substrings(word, k):
    """Returns a generator containing all substrings in word of length k"""
    for i in range(len(word) - k + 1):
        yield word[i:i+k]


def k_letters_in_common(source, words, k):
    """Given a source word and a sequence of words, find all words in the
    sequence that share a substring of length k with the source word.
    Returns a list of these words (internally, a list is an array in python).

    Uses a set of substrings so testing if a substring of a word is in the
    source word is constant time rather than linear. This is only beneficial
    if the source word is very large."""

    source_substr_set = set(get_substrings(source, k))

    def substr_in_common(word):
        for substr in get_substrings(word, k):
            if substr in source_substr_set:
                return True
        return False

    return list(filter(substr_in_common, words))


def four_letters_in_common(source, words):
    """Calls k_letters_in_common with k=4."""
    return k_letters_in_common(source, words, 4)