[Python/파이썬] LeetCode 916번 Word Subsets

https://leetcode.com/problems/word-subsets/description/

코드

from collections import defaultdict


def get_alphabet_dict(word):
    temp = defaultdict(int)
    for i in range(len(word)):
        temp[word[i]] += 1
    return temp


def wordSubsets(words1, words2):
    alphabet_dict = dict()
    for w2 in words2:
        temp = get_alphabet_dict(w2)
        for k, v in temp.items():
            if k not in alphabet_dict or alphabet_dict[k] < v:
                alphabet_dict[k] = v

    answer = []
    for w1 in words1:
        temp = get_alphabet_dict(w1)
        flag = True
        for k, v in alphabet_dict.items():
            if k not in temp or temp[k] < v:
                flag = False
                break
        if flag:
            answer.append(w1)
    return answer

 

words2에 있는 문자열들에 대해 universal인 문자열들을 구하는 문제이다.

universal하다는 것은 문자열에 있는 알파벳이 모두 포함하는 문자열이라는 말이다. (문자열 개수도 고려)

 

그래서 일단 words2에 있는 문자열들 전체에 대해 문자의 개수를 세는 딕셔너리를 만든 뒤에, 이 딕셔너리를 이용하여 words1에 있는 각 문자열이 해당 딕셔너리에 대해 universal한지 확인하는 방법으로 풀었다.