0916-单词子集

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:27 2023-09-13 16:06:27 Updated    

给你两个字符串数组 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 <= 104
  • 1 <= words1[i].length, words2[i].length <= 10
  • words1[i] 和 words2[i] 仅由小写英文字母组成
  • words1 中的所有字符串 互不相同

方法 1：将 B 合并成一个单词

想法

如果 b 是 a 的子集，那么就称 a 是 b 的超集。记录 N_{\text{“a”}}(\text{word}) 是 word 中字母 “a” 出现次数。

当我们检查 A 中的单词 wordA 是否是 wordB 的超集时，我们只需要单独检验每个字母个数：对于每个字母，有 N_{\text{letter}}(\text{wordA}) \geq N_{\text{letter}}(\text{wordB})。

现在，检验单词 wordA 是否是所有 wordB}i 的超集，我们需要检验所有 i 是否满足 N{\text{letter}}(\text{wordA}) \geq N_{\text{letter}}(\text{wordB}i)，等价于检验 N{\text{letter}}(\text{wordA}) \geq \max\limits_i(N_{\text{letter}}(\text{wordB}_i))。

例如，当我们检验 "warrior" 是否是 B = ["wrr", "wa", "or"] 的超集时，我们可以按照字母出现的最多次数将 B 中所有单词合并成一个单词 "arrow"，然后判断一次即可。

算法

将 B 合并成一个单独的单词 bmax，然后比较 A 中的所有单词 a。

[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public List<String> wordSubsets(String[] A, String[] B) {
        int[] bmax = count("");
        for (String b: B) {
            int[] bCount = count(b);
            for (int i = 0; i < 26; ++i)
                bmax[i] = Math.max(bmax[i], bCount[i]);
        }

        List<String> ans = new ArrayList();
        search: for (String a: A) {
            int[] aCount = count(a);
            for (int i = 0; i < 26; ++i)
                if (aCount[i] < bmax[i])
                    continue search;
            ans.add(a);
        }

        return ans;
    }

    public int[] count(String S) {
        int[] ans = new int[26];
        for (char c: S.toCharArray())
            ans[c - 'a']++;
        return ans;
    }
}
[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def wordSubsets(self, A, B):
        def count(word):
            ans = [0] * 26
            for letter in word:
                ans[ord(letter) - ord('a')] += 1
            return ans

        bmax = [0] * 26
        for b in B:
            for i, c in enumerate(count(b)):
                bmax[i] = max(bmax[i], c)

        ans = []
        for a in A:
            if all(x >= y for x, y in zip(count(a), bmax)):
                ans.append(a)
        return ans

复杂度分析

  • 时间复杂度：O(A+B)，其中 A 和 B 分别是 A 和 B 的单词个数。
  • 空间复杂度：O(A\text{.length} + B\text{.length})。
 Comments
On this page
0916-单词子集