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]
andwords2[i]
consist only of lowercase English letters. - All the strings of
words1
are unique.
SOLUTION:
from collections import Counter
class Solution:
def isSubset(self, ctr1, ctr2):
for c in ctr1:
if ctr2[c] < ctr1[c]:
return False
return True
def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:
univ = Counter()
for w in words2:
curr = Counter(w)
for c in curr:
univ[c] = max(univ[c], curr[c])
return [w for w in words1 if self.isSubset(univ, Counter(w))]
Top comments (0)