Problem
We are given two arraysĀ A
Ā andĀ B
Ā of words.Ā Each word is a string of lowercase letters.
Now, say thatĀ wordĀ b
Ā is a subset of wordĀ 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"
.
Now say a wordĀ a
Ā fromĀ A
Ā isĀ universalĀ if for everyĀ b
Ā inĀ B
,Ā b
Ā is a subset ofĀ a
.
Return a list of all universal words inĀ A
.Ā You can return the words in any order.
Example 1:
Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["e","o"] Output: ["facebook","google","leetcode"]
Example 2:
Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["l","e"] Output: ["apple","google","leetcode"]
Example 3:
Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["e","oo"] Output: ["facebook","google"]
Example 4:
Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["lo","eo"] Output: ["google","leetcode"]
Example 5:
Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["ec","oc","ceo"] Output: ["facebook","leetcode"]
Note:
1 <= A.length, B.length <= 10000
1 <= A[i].length, B[i].lengthĀ <= 10
A[i]
Ā andĀB[i]
Ā consist only of lowercase letters.- All words inĀ
A[i]
Ā are unique: there isn’tĀi != j
Ā withĀA[i] == A[j]
.
Solution: Hashtable
Find the max requirement for each letter from B.
Time complexity: O(|A|+|B|)
Space complexity: O(26)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
// Author: Huahua, 104 ms class Solution { public: vector<string> wordSubsets(vector<string>& A, vector<string>& B) { vector<int> req(26); for (const string& b : B) { vector<int> cur(getCount(b)); for (int i = 0; i < 26; ++i) req[i] = max(req[i], cur[i]); } vector<string> ans; for (const string& a : A) { vector<int> cur(getCount(a)); bool universal = true; for (int i = 0; i < 26; ++i) if (cur[i] < req[i]) { universal = false; break; } if (universal) ans.push_back(a); } return ans; } private: vector<int> getCount(const string& a) { vector<int> count(26); for (char c : a) ++count[c - 'a']; return count; } }; |