916.Word Subsets
916.Word Subsets
我们给出两个单词数组 A 和 B。每个单词都是一串小写字母。 现在,如果 b 中的每个字母都出现在 a 中,包括重复出现的字母,那么称单词 b 是单词 a 的子集。 例如,“wrr” 是 “warrior” 的子集,但不是 “world” 的子集。 如果对 B 中的每一个单词 b,b 都是 a 的子集,那么我们称 A 中的单词 a 是通用的。 你可以按任意顺序以列表形式返回 A 中所有的通用单词。
  • 示例 1:
1
输入:A = ["amazon","apple","facebook","google","leetcode"], B = ["e","o"]
2
输出:["facebook","google","leetcode"]
Copied!
示例 2:
1
输入:A = ["amazon","apple","facebook","google","leetcode"], B = ["l","e"]
2
输出:["apple","google","leetcode"]
Copied!
  • 示例 3:
1
输入:A = ["amazon","apple","facebook","google","leetcode"], B = ["e","oo"]
2
输出:["facebook","google"]
Copied!
  • 示例 4:
1
输入:A = ["amazon","apple","facebook","google","leetcode"], B = ["lo","eo"]
2
输出:["google","leetcode"]
Copied!
  • 示例 5:
1
输入:A = ["amazon","apple","facebook","google","leetcode"], B = ["ec","oc","ceo"]
2
输出:["facebook","leetcode"]
Copied!
  • 提示:
1
1 <= A.length, B.length <= 10000
2
1 <= A[i].length, B[i].length <= 10
3
A[i] 和 B[i] 只由小写字母组成。
4
A[i] 中所有的单词都是独一无二的,也就是说不存在 i != j 使得 A[i] == A[j]。
Copied!
方法: 通过统计26个小写字母的词频来判断是否一个单词包含另一个单词,词频都大于等于则包含。
  1. 1.
    对A向量创建一个二维向量,长度为A的size,每个向量有26个元素,表示26个小写字母,初始化词频为0。
  2. 2.
    对向量B也可以这么做,但之后判断时候则会有两层循环,导致时间复杂度增加,而另一方面,由于B的每个元素都被A中某个单词包含,则B中每个元素词频的最大值也小于等于A中某个元素词频,因此只需要对B创建一个一维向量,表示B中所有元素的字母的词频最大值。
  3. 3.
    循环遍历A中每个元素,统计各个元素中每个字母词频。
  4. 4.
    循环遍历B中每个元素,并用一个向量保存每个元素中每个字母词频最大值。
  5. 5.
    遍历A中每个元素,判断:从'a'到'z'的所有字母词频,如果存在B中的最大词频大于A的某个单词,则跳出循环。
  6. 6.
    判断是否已经遍历到最后一个字母,如果是,则表明A中该元素包含了B,将其压入result向量中。
  7. 7.
    继续循环,最后返回result向量。
1
class Solution {
2
public:
3
vector<string> wordSubsets(vector<string>& A, vector<string>& B) {
4
int sizeA = A.size();
5
int sizeB = B.size();
6
vector<vector<int>> alphaA(sizeA,vector<int>(26,0));
7
8
vector<int> alphaB1(26,0);
9
vector<string> result;
10
for(int i=0;i<sizeA;i++)
11
{
12
int sizeA1=A[i].size();
13
for(int j=0;j<sizeA1;j++)
14
{
15
alphaA[i][A[i][j]-'a']++;
16
}
17
18
}
19
for(int i=0;i<sizeB;i++)
20
{
21
int sizeB1=B[i].size();
22
vector<int> alphaB0(26,0);
23
for(int j=0;j<sizeB1;j++)
24
{
25
alphaB0[B[i][j]-'a']++;
26
}
27
for(int j=0;j<26;j++)
28
alphaB1[j] = (alphaB0[j] > alphaB1[j])?alphaB0[j]:alphaB1[j];
29
30
}
31
32
for(int i=0;i<sizeA;i++)
33
{
34
int j=0;
35
for(j;j<26;j++)
36
{
37
if(alphaB1[j] > alphaA[i][j]) break;
38
}
39
40
41
if(j == 26)
42
result.push_back(A[i]);
43
}
44
return result;
45
46
47
}
48
};
Copied!
Copy link