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 <= 104
1 <= words1[i].length, words2[i].length <= 10
words1[i]
andwords2[i]
consist only of lowercase English letters.- All the strings of
words1
are 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