[Leetcode] 916. Word Subsets

---

풀이

words2 의 글자가 words1에 포함되어있는지 확인하면 된다.

hash table을 사용하는 것으로 생각하고 문제를 풀었다.

사실 기존에 list를 통해 해결하려고 했지만 도저히 풀수가 없어서 hash로 사고를 전환하여 풀었다.

 

1.words2의 글자들로 출현 빈도가 저장된 hash table을 만든다.

2.words1의 단어의 글자들의 출현빈도가 저장된 hash table을 만든다.

3.두 hash table을 비교한다.

 

간단하지만 고민하여 푸는데 시간이 꽤나 소요되었다. 

하루하루 문제를 푸니 Medium도 손을 델 순 있는 수준이 되어 가는 것 같아 기분이 좋다.

 

코드

from collections import Counter
class Solution:
    def wordSubsets(self, words1: list[str], words2: list[str]) -> list[str]:        
        max_freq = Counter()
        for word2 in words2:
            max_freq |= Counter(word2)

        ans = []
        for word1 in words1:
            freq = Counter(word1)
            if all(freq[char] >= max_freq[char] for char in max_freq):
                ans.append(word1)
        return ans