Halo

A magic place for coding

0%

LeetCode 解题报告(328)-- 916. Word Subsets

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:

1
2
Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["e","o"]
Output: ["facebook","google","leetcode"]

Example 2:

1
2
Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["l","e"]
Output: ["apple","google","leetcode"]

Example 3:

1
2
Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["e","oo"]
Output: ["facebook","google"]

Example 4:

1
2
Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["lo","eo"]
Output: ["google","leetcode"]

Example 5:

1
2
Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["ec","oc","ceo"]
Output: ["facebook","leetcode"]

Note:

  1. 1 <= A.length, B.length <= 10000
  2. 1 <= A [i].length, B [i].length <= 10
  3. A [i] and B [i] consist only of lowercase letters.
  4. All words in A [i] are unique: there isn’t i != j with A [i] == A [j].

Analysis

   题目给出 AB 两个字符串数组,定义 A 中的某个单词 auniversal 如果所有在 B 中出现的字母都在 a 出现,包括出现的次数。因为这里有次数的要求,所以我们首先找到最低条件:** 在 B 中每个字符都需要出现多少次 **。例如 B = ["facebook", leetcode"],那么它o的最大出现次数就是 2,来自于facebook 这个单词。

   然后我们再对 A 的单词逐个遍历,同样地计算出这个单词每个字母出现的次数,然后对比每个字母出现次数是否都大于等于 B 的最低要求,如果都满足,这个单词就是 universal,加入到答案中;否则就检查下一个。


Solution

   无


Code

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
33
34
35
36
37
38
class Solution {
public:
vector<string> wordSubsets(vector<string>& A, vector<string>& B) {
int size1 = A.size ();
int size2 = B.size ();

int maxCount [26] = {0};
for (int i = 0; i < size2; i++) {
vector<int> c = getCount (B [i]);
for (int j = 0; j < 26; j++) {
maxCount [j] = max (maxCount [j], c [j]);
}
}

vector<string> result;
for (int i = 0; i < size1; i++) {
vector<int> c = getCount (A [i]);
int j = 0;
for (j = 0; j < 26; j++) {
if (c [j] < maxCount [j]) {
break;
}
}
if (j == 26) {
result.push_back (A [i]);
}
}
return result;
}
private:
vector<int> getCount(string str) {
vector<int> result(26, 0);
for (int i = 0; i < str.size (); i++) {
result [str [i] - 'a']++;
}
return result;
}
};

Summary

   这道题目的关键点在于找到判断 universal 的最低条件。因为每次都需要和 B 中所有的单词比较,所以可以先把这个最低条件求出来,然后每次只需要和这个条件做比较即可。这道题目的分享到这里,感谢你的支持!

Welcome to my other publishing channels