LeetCode 916. 单词子集(计数)

1. 题目

我们给出两个单词数组 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]。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/word-subsets
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

  • 统计B中每个单词的每种字符的数量,取最大的频数
  • 再统计a字符串,看是否每个字符计数都大于上面的计数
class Solution {
public:
    vector<string> wordSubsets(vector<string>& A, vector<string>& B) {
    	vector<int> countB(26,0);
    	for(auto& bi : B)
    	{
            vector<int> countb(26,0);
            for(char ch : bi)
    			countb[ch-'a']++;
            for(int i = 0; i < 26; ++i)
                countB[i] = max(countB[i],countb[i]);//取较大的
        }

    	vector<string> ans;
    	bool ok;
    	for(auto& Ai : A)
    	{
            vector<int> countai(26,0);
    		ok = true;
    		for(char ch : Ai)
                countai[ch-'a']++;
    		for(int i = 0; i < 26; ++i)
            {
                if(countai[i] < countB[i])//不满足
                {
                    ok = false;
                    break;
                }
            }
            if(ok)
    			ans.push_back(Ai);
    	}
    	return ans;
    }
};

348 ms 88.6 MB

上一篇:React Native环境搭建及配置问题


下一篇:[转帖]Facebook第四季度营收211亿美元 净利同比增7%