[medium] 916. Word Subsets

문제

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

Word Subsets - LeetCode

---

풀이방법

words1의 단어들 중 words2의 모든 단어를 subset으로 가질 수 있는 단어들을 찾는 문제이다.

시간 절약을 위해 words2에 대한 전처리가 매우 중요했다.

• words2의 단어들 중에 중복되는게 있을 수 있으므로 set으로 변환했다가 다시 list로 변환함으로써 중복을 제거한다.
• words2의 모든 단어들을 커버할 수 있는 하나의 dict를 구성한다.

전체 words2에 대해 구성한 dict 를 포함하는 words1의 단어들을 리스트에 저장한다.

반응형

---

코드

class Solution:
    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:
        def makedic(word): #word에 속한 알파벳들에 대한 딕셔너리 구성
            dic = {}
            for c in word:
                if c in dic.keys():
                    dic[c] += 1
                else:
                    dic[c] =1
            return dic
        
        def checkdic(dict2, dict_total): #dict2의 구성요소들을 dict_total로 통합
            for key in dict2.keys():
                if key not in dict_total.keys():
                    dict_total[key] = dict2[key]
                elif dict_total[key] < dict2[key]:
                    dict_total[key] = dict2[key]
            return dict_total
        
        result = []
        words2 = list(set(words2)) #중복제거
        dict_total = {}
        for w2 in words2:
            dict2 = {}
            for c in w2:
                if c in dict2.keys():
                    dict2[c] += 1
                else:
                    dict2[c] = 1
            dict_total = checkdic(dict2, dict_total)

        for w1 in words1:
            dict1 = makedic(w1)
            flag = True
            for key in dict_total.keys():
                if key not in dict1:
                    flag = False
                    break
                if dict_total[key] > dict1[key]:
                    flag = False
                    break
            if flag:
                result.append(w1)
        return result