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).
1import java.util.ArrayList;
2import java.
This Java solution uses an integer array of size 26 to store character frequencies, making it efficient in terms of both space and time for access. We compute the aggregate maximum frequency needed, and check words in words1 against this frequency array directly.