。单词子集

916。单词子集

难度：中等

主题：数组、哈希表、字符串

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

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

• 例如，“wrr”是“warrior”的子集，但不是“world”的子集。

words1 中的字符串 a 是通用如果对于words2 中的每个字符串 b，b 是 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"]

约束：

• 1 4
• 1
• Words1[i] 和 Words2[i] 仅由小写英文字母组成。
• words1 的所有字符串都是唯一。

解决方案：

我们需要识别words1中“通用”的单词，这意味着words2中的每个字符串都是words1中单词的子集。

方法：

1. 统计单词中字符的出现频率2：

   • 首先，我们需要确定words2 中所有字符串中每个字符的最大计数。这为我们提供了每个字符作为子集所需的出现次数。

2. 检查words1中的每个单词：

   • 对于words1中的每个单词，计算每个字符的频率。
   • 如果words1中的单词中的字符数满足或超过words2中所需的计数，则该单词是通用的。

3. 返回通用词：

   • 检查完words1中的所有单词后，返回通用的单词。

让我们用 PHP 实现这个解决方案：916。单词子集

<?php /**
 * @param String[] $words1
 * @param String[] $words2
 * @return String[]
 */
function wordSubsets($words1, $words2) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$words1 = ["amazon", "apple", "facebook", "google", "leetcode"];
$words2 = ["e", "o"];
print_r(wordSubsets($words1, $words2));  // Output: ["facebook", "google", "leetcode"]

$words2 = ["l", "e"];
print_r(wordSubsets($words1, $words2));  // Output: ["apple", "google", "leetcode"]
?>

解释：

1. 为words2构建频率图：我们循环遍历words2中的每个单词并计算每个字符的频率。我们跟踪 Words2 中所有单词中每个字符所需的最大频率。

2. 检查words1单词：对于words1中的每个单词，我们计算每个字符的频率并将其与words2中所需的频率进行比较。如果该单词满足所有字符的要求，则被认为是通用的。

3. 结果：我们将所有通用单词存储在结果数组中并在最后返回。

时间复杂度：

• 构建words2的频率图： O(n * m)，其中n是words2的长度，m是words2中单词的平均长度。
• 检查单词1： O(k * m)，其中k是单词1的长度，m是单词1中单词的平均长度。
• 总时间复杂度约为O(n * m k * m).

这种方法确保我们有效地检查每个单词并满足问题的约束。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是。单词子集的详细内容。更多信息请关注PHP中文网其他相关文章！