LeetCode 솔루션 분류
[7/30] 916. Word Subsets
본문
Medium
2162180Add to ListShareYou 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 <= 1041 <= words1[i].length, words2[i].length <= 10words1[i]andwords2[i]consist only of lowercase English letters.- All the strings of
words1are unique.
Accepted
88,270
Submissions
164,125
태그
#Google
관련자료
-
링크
댓글 1
학부유학생님의 댓글
- 익명
- 작성일
Runtime: 1334 ms, faster than 46.34% of Python3 online submissions for Word Subsets.
Memory Usage: 18.9 MB, less than 23.33% of Python3 online submissions for Word Subsets.
Memory Usage: 18.9 MB, less than 23.33% of Python3 online submissions for Word Subsets.
import collections
class Solution:
def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:
word2_union = collections.defaultdict(int)
for word in words2:
temp_counter = collections.Counter(word)
for key in temp_counter:
word2_union[key] = max(word2_union[key], temp_counter[key])
res = []
for word in words1:
temp_counter = collections.Counter(word)
res.append(word)
for key in word2_union:
if key not in temp_counter or temp_counter[key] < word2_union[key]:
res.pop(); break;
return res
