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.
"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 <= 1041 <= words1[i].length, words2[i].length <= 10words1[i] and words2[i] consist only of lowercase English letters.words1 are unique.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.
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.
C++
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.
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.
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.
JavaScript
Time Complexity: O(N * S + M * T), Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Frequency Map Aggregation | 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. |
| Character Set Checking | Time Complexity: O(N * S + M * T), Space Complexity: O(1). |
Subsets - Backtracking - Leetcode 78 • NeetCode • 341,241 views views
Watch 9 more video solutions →Practice Word Subsets with our built-in code editor and test cases.
Practice on FleetCode