文章目录

• 题目
• • 标题和出处
  • 难度
  • 题目描述
  • • 要求
    • 示例
    • 数据范围
• 解法
• • 思路和算法
  • 代码
  • 复杂度分析

题目

标题和出处

标题：单词子集

出处：916. 单词子集

难度

4 级

题目描述

要求

给你两个字符串数组 words1\texttt{words1}words1 和 words2\texttt{words2}words2。

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

• 例如，"wrr"\texttt{"wrr"}"wrr" 是 "warrior"\texttt{"warrior"}"warrior" 的子集，但不是 "world"\texttt{"world"}"world" 的子集。

对 words1\texttt{words1}words1 中的单词 a\texttt{a}a，如果对 words2\texttt{words2}words2 中的每一个单词 b\texttt{b}b，b\texttt{b}b 都是 a\texttt{a}a 的子集，那么我们称 a\texttt{a}a 是通用单词。

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

示例

示例 1：

输入：words1=["amazon","apple","facebook","google","leetcode"],words2=["e","o"]\texttt{words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]}words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]
输出：["facebook","google","leetcode"]\texttt{["facebook","google","leetcode"]}["facebook","google","leetcode"]

示例 2：

输入：words1=["amazon","apple","facebook","google","leetcode"],words2=["l","e"]\texttt{words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["l","e"]}words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["l","e"]
输出：["apple","google","leetcode"]\texttt{["apple","google","leetcode"]}["apple","google","leetcode"]

数据范围

• 1≤words1.length,words2.length≤104\texttt{1} \le \texttt{words1.length, words2.length} \le \texttt{10}^\texttt{4}1≤words1.length, words2.length≤104
• 1≤words1[i].length,words2[i].length≤10\texttt{1} \le \texttt{words1[i].length, words2[i].length} \le \texttt{10}1≤words1[i].length, words2[i].length≤10
• words1[i]\texttt{words1[i]}words1[i] 和 words2[i]\texttt{words2[i]}words2[i] 仅由小写英语字母组成
• words1\texttt{words1}words1 中的所有字符串互不相同

解法

思路和算法

数组 words1\textit{words}_1words1​ 中的单词 word\textit{word}word 是通用单词，等价于单词 word\textit{word}word 中的每个字母的出现次数都不小于数组 words2\textit{words}_2words2​ 中的任意一个单词中的相同字母的出现次数。

最直观的做法是，首先统计出数组 words2\textit{words}_2words2​ 中的每个单词中的每个字母的出现次数，然后遍历数组 words1\textit{words}_1words1​，对于每个单词 aaa，遍历数组 words2\textit{words}_2words2​ 中的每个单词 bbb，判断单词 aaa 中的每个字母的出现次数是否都不小于单词 bbb 中的相同字母的出现次数。假设数组 words1\textit{words}_1words1​ 和 words2\textit{words}_2words2​ 的长度分别是 mmm 和 nnn，则上述做法的时间复杂度至少为 O(mn)O(mn)O(mn)，由于 mmm 和 nnn 的最大值可达 10410^4104，因此上述做法的时间复杂度过高，需要优化。

由于通用单词中的每个字母的出现次数不小于数组 words2\textit{words}_2words2​ 中的任意一个单词中的相同字母的出现次数，因此只需要记录每个字母在数组 words2\textit{words}_2words2​ 中的单词中的最大出现次数即可，通用单词中的每个字母的出现次数不小于相同字母在数组 words2\textit{words}_2words2​ 中的单词中的最大出现次数。

首先遍历数组 words2\textit{words}_2words2​ 中的每个单词，并记录每个字母在数组 words2\textit{words}_2words2​ 中的单词中的最大出现次数，然后遍历数组 words1\textit{words}_1words1​ 中的每个单词 word\textit{word}word，根据单词 word\textit{word}word 中的每个字母的出现次数是否都不小于相同字母在数组 words2\textit{words}_2words2​ 中的单词中的最大出现次数，判断单词 word\textit{word}word 是不是通用单词，将通用单词添加到结果列表。

实现方面，由于数组 words1\textit{words}_1words1​ 和 words2\textit{words}_2words2​ 中的每个单词只包含小写英语字母，因此可以使用长度为 262626 的数组代替哈希表记录每个字母的出现次数。

代码

class Solution {public List wordSubsets(String[] words1, String[] words2) {int[] unionCounts = new int[26];for (String word : words2) {int[] letterCounts = getLetterCounts(word);for (int i = 0; i < 26; i++) {unionCounts[i] = Math.max(unionCounts[i], letterCounts[i]);}}List subsets = new ArrayList();for (String word : words1) {boolean isUniversal = true;int[] letterCounts = getLetterCounts(word);for (int i = 0; i < 26; i++) {if (letterCounts[i] < unionCounts[i]) {isUniversal = false;break;}}if (isUniversal) {subsets.add(word);}}return subsets;}public int[] getLetterCounts(String word) {int[] letterCounts = new int[26];int length = word.length();for (int i = 0; i < length; i++) {char c = word.charAt(i);letterCounts[c - 'a']++;}return letterCounts;}
}

复杂度分析

• 时间复杂度：O(L1+L2+∣Σ∣×(m+n))O(L_1 + L_2 + |\Sigma| \times (m + n))O(L1​+L2​+∣Σ∣×(m+n))，其中 mmm 和 nnn 分别是数组 words1\textit{words}_1words1​ 和 words2\textit{words}_2words2​ 的长度，L1L_1L1​ 和 L2L_2L2​ 分别是数组 words1\textit{words}_1words1​ 和 words2\textit{words}_2words2​ 中的单词长度之和，Σ\SigmaΣ 是字符集，这道题中 Σ\SigmaΣ 是全部小写英语字母，∣Σ∣=26|\Sigma| = 26∣Σ∣=26。
  首先需要遍历数组 words2\textit{words}_2words2​ 中的全部单词并记录每个字母的最大出现次数，需要 O(L2+∣Σ∣×n)O(L_2 + |\Sigma| \times n)O(L2​+∣Σ∣×n) 的时间。
  然后需要遍历数组 words1\textit{words}_1words1​ 中的全部单词并判断每个单词是不是通用单词，需要 O(L1+∣Σ∣×m)O(L_1 + |\Sigma| \times m)O(L1​+∣Σ∣×m) 的时间。
  因此总时间复杂度是 O(L1+L2+∣Σ∣×(m+n))O(L_1 + L_2 + |\Sigma| \times (m + n))O(L1​+L2​+∣Σ∣×(m+n))。

• 空间复杂度：O(∣Σ∣)O(|\Sigma|)O(∣Σ∣)，其中 Σ\SigmaΣ 是字符集，这道题中 Σ\SigmaΣ 是全部小写英语字母，∣Σ∣=26|\Sigma| = 26∣Σ∣=26。空间复杂度主要取决于哈希表，需要使用哈希表记录每个字母在数组 words2\textit{words}_2words2​ 中的单词中的最大出现次数，以及在遍历数组 words1\textit{words}_1words1​ 时需要使用哈希表记录遍历到的单词中的每个字母的出现次数。注意返回值不计入空间复杂度。