916. 单词子集

题目

给你两个字符串数组 words1 和 words2。

现在，如果 b 中的每个字母都出现在 a 中，包括重复出现的字母，那么称字符串 b 是字符串 a 的 子集 。

例如，”wrr” 是 “warrior” 的子集，但不是 “world” 的子集。
如果对 words2 中的每一个单词 b，b 都是 a 的子集，那么我们称 words1 中的单词 a 是 通用单词 。

以数组形式返回 words1 中所有的通用单词。你可以按 任意顺序 返回答案。

示例 1：

输入：words1 = [“amazon”,”apple”,”facebook”,”google”,”leetcode”], words2 = [“e”,”o”]
输出：[“facebook”,”google”,”leetcode”]

示例 2：

输入：words1 = [“amazon”,”apple”,”facebook”,”google”,”leetcode”], words2 = [“l”,”e”]
输出：[“apple”,”google”,”leetcode”]

示例 3：

输入：words1 = [“amazon”,”apple”,”facebook”,”google”,”leetcode”], words2 = [“e”,”oo”]
输出：[“facebook”,”google”]

示例 4：

输入：words1 = [“amazon”,”apple”,”facebook”,”google”,”leetcode”], words2 = [“lo”,”eo”]
输出：[“google”,”leetcode”]

示例 5：

输入：words1 = [“amazon”,”apple”,”facebook”,”google”,”leetcode”], words2 = [“ec”,”oc”,”ceo”]
输出：[“facebook”,”leetcode”]

提示：

1 <= words1.length, words2.length <= 10^4
1 <= words1[i].length, words2[i].length <= 10
words1[i] 和 words2[i] 仅由小写英文字母组成
words1 中的所有字符串 互不相同

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

思路

因为通用单词要满足中单词都是其子集，所以对于任意一个小写字母，个数要不小于中出现频率最高的。

先遍历，统计每个字母出现的最高频率，然后看中有哪些单词可以当做通用单词。

这个题最多属于中下难度吧。

代码

class Solution {
    public List<String> wordSubsets(String[] words1, String[] words2) {
        int[] cnt = new int[26];
        for (String word : words2) {
            int[] tmp = new int[26];
            for (int i = 0; i < word.length(); i++) {
                tmp[word.charAt(i) - 'a']++;
            }
            for (int i = 0; i < 26; i++) {
                cnt[i] = Math.max(cnt[i], tmp[i]);
            }
        }
        List<String> ans = new ArrayList<>();
        for (String word : words1) {
            int[] tmp = new int[26];
            for (int i = 0; i < word.length(); i++) {
                tmp[word.charAt(i) - 'a']++;
            }
            boolean flag = true;
            for (int i = 0; i < 26; i++) {
                if (tmp[i] < cnt[i]) {
                    flag = false;
                }
            }
            if (flag) {
                ans.add(word);
            }
        }
        return ans;
    }
}