leetcode - 916. Word Subsets
DescriptionYou 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 <= 10^4
1 <= words1.length, words2.length <= 10
words1 and words2 consist only of lowercase English letters.
All the strings of words1 are unique.
Solution
A little bit tricky and one take-away is: if the total time complexity is around 1 0 8 10^8 108, don’t try it, it will be TLE.
The core idea is, we build a hashmap of words2, and iterate all the strings in words1 to decide if we want to select it. The tricky part is how we build the hash map.
Because oo won’t be a subset of aeiou, but ['ao', 'eo'] would be a subset of aeiou, so to build the hash map, we just need to store the maximum frequency of the string in words2.
Time complexity: o ( w o r d s 2. l e n + w o r d s 1. l e n ) o(words2.len + words1.len) o(words2.len+words1.len)
Space complexity: o ( 1 ) o(1) o(1)
Code
class Solution:
def wordSubsets(self, words1: List, words2: List) -> List:
words2_fre = * 26
for each_word in words2:
ch_cnt = collections.Counter(each_word)
for each_ch, each_cnt in ch_cnt.items():
ch_index = ord(each_ch) - ord('a')
words2_fre = max(words2_fre, each_cnt)
res = []
for each_word in words1:
ch_cnt = collections.Counter(each_word)
is_candidate = True
for i in range(26):
if ch_cnt.get(chr(i + ord('a')), 0) < words2_fre:
is_candidate = False
break
if is_candidate:
res.append(each_word)
return res
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]