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]
andB[i]
consist only of lowercase letters.- All words in
A[i]
are unique: there isn’ti != j
withA[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; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment