916.单词子集

单词子集

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

如果 b 是 a 的子集，即 b 中的每个字母都在 a 中出现，则称 a 是 b 的超集。

返回 words1 中所有满足对于 words2 中的每个单词 b，a 都是 b 的超集的单词 a。

示例 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”]

提示：

• 1 <= words1.length, words2.length <= 10^4
• 1 <= words1[i].length, words2[i].length <= 10
• words1[i] 和 words2[i] 仅由小写英文字母组成

解析

先统计 words2 中每个字母的最大需求次数，然后遍历 words1 筛选满足条件的单词。

var wordSubsets = function (words1, words2) {
  // 统计 words2 中每个字母的最大需求
  const need = new Array(26).fill(0);
  for (const word of words2) {
    const count = new Array(26).fill(0);
    for (const c of word) {
      count[c.charCodeAt(0) - 97]++;
    }
    for (let i = 0; i < 26; i++) {
      need[i] = Math.max(need[i], count[i]);
    }
  }

  const result = [];
  for (const word of words1) {
    const count = new Array(26).fill(0);
    for (const c of word) {
      count[c.charCodeAt(0) - 97]++;
    }
    let valid = true;
    for (let i = 0; i < 26; i++) {
      if (count[i] < need[i]) {
        valid = false;
        break;
      }
    }
    if (valid) result.push(word);
  }

  return result;
};

时间复杂度 O(m + n)，其中 m 是 words1 的总字符数，n 是 words2 的总字符数。空间复杂度 O(1)。