(Python3) - LeetCode (Medium) : 916. Word Subsets

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

전수조사로 해결한 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

정답변수 ans, words2의 알파뱃의 빈도수를 저장할 hash map words2_map을 선언 후 적절히 저장합니다. words2_map에 빈도 수를 저장할 때는 각 알파뱃별 빈도수를 단순히 1씩 증가시키는 것이 아니고 각 단어별 가장 많이 나온 빈도수를 저장해야합니다. words2 가 각각 ["e", "oo"], ["eo", "lo"] 라면 {e:1, o:2}, {e:1,l:1,o:1} 형태로 알파뱃이 o인 부분에 있어 한번에 최대로 나온 값을 저장합니다.

📔 풀이과정

words1의 길이는 최대 1만과 각 단어의 최대길이 10을 곱해도 10만의 시간복잡도로 subset을 구할 수 있습니다.

 

1. words1에 대해 for loop를 수행하며 다음을 진행합니다.  1-1. 각 단어의 문자와 빈도수를 words1_map에 저장해줍니다. 1-2. words2_map의 items를 순회하며 words1_map의 빈도수가 words2_map문자의 빈도 수보다 작다면 subset이 아니므로 flag를 False로 만들어 줍니다. 1-3. answer에 is_flag라면 현재 word를 넣어줍니다. 

📔 정답 출력 | 반환

answer를 반환합니다.

---

📕 Code

📔 Python3

from collections import defaultdict
class Solution:
    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:
        answer = []
        words2_map = defaultdict(int)
        for word in words2:
            words2_char_map = defaultdict(int)
            for char in word:
                words2_char_map[char] += 1
            for char, freq in words2_char_map.items():
                words2_map[char] = max(words2_map[char], freq)
        for word in words1:
            words1_map = defaultdict(int)
            is_valid = True
            for char in word:
                words1_map[char] += 1
            for char, freq in words2_map.items():
                if words1_map[char] < freq:
                    is_valid = False
                    break
            if is_valid:
                answer.append(word)
        return answer

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.