[LeetCode] 916. Word Subsets

916. Word Subsets

Medium

 

You are given two string arrays words1 and words2.

A string b is a subset of string a if every letter in b occurs in a including multiplicity.

• For example, "wrr" is a subset of "warrior" but is not a subset of "world".

A string a from words1 is universal if for every string b in words2, b is a subset of a.

Return an array of all the universal strings in words1. You may return the answer in any order.

 

Example 1:

Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]
Output: ["facebook","google","leetcode"]

Example 2:

Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["l","e"]
Output: ["apple","google","leetcode"]

 

Constraints:

• 1 <= words1.length, words2.length <= 104
• 1 <= words1[i].length, words2[i].length <= 10
• words1[i] and words2[i] consist only of lowercase English letters.
• All the strings of words1 are unique.

 

---

문제 해설

문제 접근

1. 단어 세트 두개가 주어진다.
2. 두번째 단어 (두번째 단어 세트)에 들어있는 모든 문자가 하나의 단어(첫번째 단어 세트) 안에 포함이 되어있는 Subset 이라면 답으로 반환
3. 모든 단어는 길이가 1부터 10^4 까지 이다.
4. 두번째 단어를 모두세고 첫번째 단어를 모두 샌다면 N^2 이 되고, 각 단어들을 확인하려면 N^3 이 된다.
5. N^3 은 시간 초과가 될것이다.
6. 모든 단어를 각각 확인하지 않고 다른 방법이 필요하다.

문제 풀이

1. 딕셔너리(해쉬맵) 에 한꺼번에 처리할 수 있는 값을 담아야한다.
2. 첫번째 단어가 두번째 단어 세트의 모든 단어가 들어있는지 확인해야한다. 
3. 예를들어, 첫번째 단어가 "abcdd" 이고 두번째 단어들이 "abdd", "aabdd" 라면, 성립되지 않는다.
4. "aabdd" 에서 a가 두개이기 때문에 첫번째 단어와 조건이 성립되지 않는다. 
5. 딕셔너리를 두번째 단어 세트의 알파벳 갯수로 만들되, 최대값만 가지고 있으면 한번의 처리로 끝낼 수 있다.
6. 예제로 구상한다면, {a : 2, b : 1, d : 2} 가 된다, a 최대 갯수 계산시 답을 걸러낼 수 있다. 

소스코드 

class Solution:
    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:
        def count(word):
            hashmap = defaultdict(int)
            for latter in word:
                hashmap[latter] += 1
            return hashmap
        hashmap2 = defaultdict(int)
        for word in words2:
            for k, v in count(word).items():
                hashmap2[k] = max(hashmap2[k], v)
        ans = []
        for word in words1:
            hashmap3 = count(word)
            flag = True
            for k, v in hashmap2.items():
                if hashmap3[k] < hashmap2[k]:
                    flag = False
            if flag:
                ans.append(word)
        return ans