Sponsored
Sponsored
This approach involves using a frequency map to determine the maximum frequency of each letter required by words2 that must be present in each word in words1 to be considered universal. We then check each word in words1 to see if it satisfies these maximum frequency requirements.
Time Complexity: O(N * S + M * T), where N is the length of words1, M is the length of words2, S is the average length of a word in words1, and T is the average length of a word in words2. The space complexity is O(1), as we are using a fixed character set.
1from collections import Counter
2
3def wordSubsets(words1, words2):
4 max_freq = Counter()
5 for word in words2:
6 for letter, freq in Counter(word).items():
7 max_freq[letter] = max(max_freq[letter], freq)
8
9 result = []
10 for word in words1:
11 word_freq = Counter(word)
12 if all(word_freq[letter] >= max_freq[letter] for letter in max_freq):
13 result.append(word)
14
15 return result
16
17words1 = ["amazon","apple","facebook","google","leetcode"]
18words2 = ["e","o"]
19print(wordSubsets(words1, words2)) # Output: ['facebook','google','leetcode']This solution first calculates the maximum frequency for each letter that appears in words2 using a counter. Then, it iterates over words1 to verify if each word contains at least the maximum frequencies for all letters calculated. If so, it adds the word to the result list.
In this approach, we create a character frequency check vector for words2 and verify each word in words1 against this vector. Instead of a hashmap, we'll use arrays as fixed length makes space and access efficient.
Time Complexity: O(N * S + M * T), Space Complexity: O(1).
1function wordSubsets(words1, words2) {
2 let maxFreq
In the JavaScript approach, we maintain an array for the maximum frequency of each character required across all words2. A helper function is used to count character frequencies. Words from words1 are compared against this dataset.