916.Word Subsets

916.Word Subsets

我们给出两个单词数组 A 和 B。每个单词都是一串小写字母。 现在，如果 b 中的每个字母都出现在 a 中，包括重复出现的字母，那么称单词 b 是单词 a 的子集。 例如，“wrr” 是 “warrior” 的子集，但不是 “world” 的子集。 如果对 B 中的每一个单词 b，b 都是 a 的子集，那么我们称 A 中的单词 a 是通用的。 你可以按任意顺序以列表形式返回 A 中所有的通用单词。

• 示例 1：

输入：A = ["amazon","apple","facebook","google","leetcode"], B = ["e","o"]
输出：["facebook","google","leetcode"]

示例 2：

输入：A = ["amazon","apple","facebook","google","leetcode"], B = ["l","e"]
输出：["apple","google","leetcode"]

• 示例 3：

输入：A = ["amazon","apple","facebook","google","leetcode"], B = ["e","oo"]
输出：["facebook","google"]

• 示例 4：

输入：A = ["amazon","apple","facebook","google","leetcode"], B = ["lo","eo"]
输出：["google","leetcode"]

• 示例 5：

输入：A = ["amazon","apple","facebook","google","leetcode"], B = ["ec","oc","ceo"]
输出：["facebook","leetcode"]

• 提示：

1 <= A.length, B.length <= 10000
1 <= A[i].length, B[i].length <= 10
A[i] 和 B[i] 只由小写字母组成。
A[i] 中所有的单词都是独一无二的，也就是说不存在 i != j 使得 A[i] == A[j]。

方法： 通过统计26个小写字母的词频来判断是否一个单词包含另一个单词，词频都大于等于则包含。

1. 对A向量创建一个二维向量，长度为A的size，每个向量有26个元素，表示26个小写字母，初始化词频为0。

2. 对向量B也可以这么做，但之后判断时候则会有两层循环，导致时间复杂度增加，而另一方面，由于B的每个元素都被A中某个单词包含，则B中每个元素词频的最大值也小于等于A中某个元素词频，因此只需要对B创建一个一维向量，表示B中所有元素的字母的词频最大值。

3. 循环遍历A中每个元素，统计各个元素中每个字母词频。

4. 循环遍历B中每个元素，并用一个向量保存每个元素中每个字母词频最大值。

5. 遍历A中每个元素，判断：从'a'到'z'的所有字母词频，如果存在B中的最大词频大于A的某个单词，则跳出循环。

6. 判断是否已经遍历到最后一个字母，如果是，则表明A中该元素包含了B，将其压入result向量中。

7. 继续循环，最后返回result向量。

class Solution {
public:
    vector<string> wordSubsets(vector<string>& A, vector<string>& B) {
        int sizeA = A.size();
        int sizeB = B.size();
        vector<vector<int>> alphaA(sizeA,vector<int>(26,0));

        vector<int> alphaB1(26,0);
        vector<string> result;
        for(int i=0;i<sizeA;i++)
        {
            int sizeA1=A[i].size();
            for(int j=0;j<sizeA1;j++)
            {
                alphaA[i][A[i][j]-'a']++;
            }

        }
            for(int i=0;i<sizeB;i++)
        {
            int sizeB1=B[i].size();
            vector<int> alphaB0(26,0);
            for(int j=0;j<sizeB1;j++)
            {
                alphaB0[B[i][j]-'a']++;
            }
            for(int j=0;j<26;j++)
                alphaB1[j] = (alphaB0[j] > alphaB1[j])?alphaB0[j]:alphaB1[j];

        }

        for(int i=0;i<sizeA;i++)
        {
            int j=0;
            for(j;j<26;j++)
            {
                if(alphaB1[j] > alphaA[i][j]) break;
            }


            if(j == 26)
                result.push_back(A[i]);
        }
        return result;


    }
};