916. 单词子集

🟠   🔖  数组 哈希表 字符串  🔗 力扣 LeetCode

题目

You are given two string arrays words1 and words2.

A string b is a subset of string 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".

A string a from words1 is universal if for every string b in words2, b is a subset of a.

Return an array of all the universal strings in words1. You may return the answer in any order.

Example 1:

Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]

Output: ["facebook","google","leetcode"]

Example 2:

Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["l","e"]

Output: ["apple","google","leetcode"]

Constraints:

• 1 <= words1.length, words2.length <= 10^4
• 1 <= words1[i].length, words2[i].length <= 10
• words1[i] and words2[i] consist only of lowercase English letters.
• All the strings of words1 are unique.

题目大意

给你两个字符串数组 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 中的所有字符串 互不相同

解题思路

1. 构建 words2 的最大字符需求

   • words2 中的每个单词对字母的需求会叠加，例如如果 words2 包含 "aabb" 和 "ab", 那么最终的需求是 a:2, b:2。
   • 我们可以用一个数组 chars 来记录所有字母的最大需求，每个单词遍历时都更新 chars 中的最大值。
   • 初始化一个数组 chars 长度为 26，表示字母 'a' 到 'z' 的需求次数，初始值为 0。
   • 遍历 words2，对每个单词生成一个临时计数数组 temp，记录该单词中每个字母的出现次数，然后更新 chars 中的最大值。

2. 遍历 words1 并检查是否满足需求

   • 对于 words1 中的每个单词，检查它是否能满足 chars 中的需求。
   • 用另一个数组 temp 来表示需求，并在遍历单词时减少对应的字母计数。
   • 遍历 words1，对每个单词复制一个 temp 数组（基于 chars），并减少对应字母的需求计数。如果 temp 数组中所有值都小于等于 0，则将该单词加入结果数组。

3. 返回结果数组。

复杂度分析

• 时间复杂度：O(n2 * m2 + n1 * m1)
  • 构建 chars 数组需要遍历 words2，时间复杂度为 O(n2 * m2)，其中 n2 是 words2 的长度，m2 是单词的平均长度。
  • 检查每个单词是否满足条件需要遍历 words1，时间复杂度为 O(n1 * m1)，其中 n1 是 words1 的长度，m1 是单词的平均长度。
  • 总时间复杂度为 O(n2 * m2 + n1 * m1)。
• 空间复杂度：O(1)，使用了两个辅助数组 chars 和 temp，每个长度为 26。

代码

/**
 * @param {string[]} words1
 * @param {string[]} words2
 * @return {string[]}
 */
var wordSubsets = function (words1, words2) {
	let chars = new Array(26).fill(0);
	for (let word of words2) {
		let temp = new Array(26).fill(0);
		for (let char of word) {
			temp[char.charCodeAt() - 97]++;
		}
		for (let i = 0; i <= 26; i++) {
			chars[i] = Math.max(chars[i], temp[i]);
		}
	}

	let res = [];

	for (let word of words1) {
		let temp = [...chars];
		for (let char of word) {
			temp[char.charCodeAt() - 97]--;
		}
		if (temp.filter((i) => i > 0).length == 0) {
			res.push(word);
		}
	}
	return res;
};