916-WordSubsets

Word Subsets

Problem can be found in here!

Solution: Hash Table

def wordSubsets(words1: List[str], words2: List[str]) -> List[str]:
    counter = defaultdict(int)
    for word in words2:
        char_set = Counter(word)
        for key, value in char_set.items():
            counter[key] = max(counter[key], value)

    matched_words = []
    for word in words1:
        char_set = Counter(word)
        for key, value in counter.items():
            if char_set[key] < value:
                break
        else:
            matched_words.append(word)

    return matched_words

Time Complexity: , Space Complexity: , where n and m are the total number of characters in words1 and words2, respectively.