Question

916. 单词子集

English Version

题目描述

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

解法

方法一：计数

遍历 words2 中的每个单词 b，统计每个字母出现的最大次数，记为 cnt。

然后遍历 words1 中的每个单词 a，统计每个字母出现的次数，记为 t。如果 cnt 中的每个字母的出现次数都不大于 t 中的出现次数，则 a 是通用单词，将其加入答案。

时间复杂度 $O(L)$，其中 $L$ 为 words1 和 words2 中所有单词的长度之和。

class Solution:
  def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:
    cnt = Counter()
    for b in words2:
      t = Counter(b)
      for c, v in t.items():
        cnt[c] = max(cnt[c], v)
    ans = []
    for a in words1:
      t = Counter(a)
      if all(v <= t[c] for c, v in cnt.items()):
        ans.append(a)
    return ans

class Solution {
  public List<String> wordSubsets(String[] words1, String[] words2) {
    int[] cnt = new int[26];
    for (var b : words2) {
      int[] t = new int[26];
      for (int i = 0; i < b.length(); ++i) {
        t[b.charAt(i) - 'a']++;
      }
      for (int i = 0; i < 26; ++i) {
        cnt[i] = Math.max(cnt[i], t[i]);
      }
    }
    List<String> ans = new ArrayList<>();
    for (var a : words1) {
      int[] t = new int[26];
      for (int i = 0; i < a.length(); ++i) {
        t[a.charAt(i) - 'a']++;
      }
      boolean ok = true;
      for (int i = 0; i < 26; ++i) {
        if (cnt[i] > t[i]) {
          ok = false;
          break;
        }
      }
      if (ok) {
        ans.add(a);
      }
    }
    return ans;
  }
}

class Solution {
public:
  vector<string> wordSubsets(vector<string>& words1, vector<string>& words2) {
    int cnt[26] = {0};
    int t[26];
    for (auto& b : words2) {
      memset(t, 0, sizeof t);
      for (auto& c : b) {
        t[c - 'a']++;
      }
      for (int i = 0; i < 26; ++i) {
        cnt[i] = max(cnt[i], t[i]);
      }
    }
    vector<string> ans;
    for (auto& a : words1) {
      memset(t, 0, sizeof t);
      for (auto& c : a) {
        t[c - 'a']++;
      }
      bool ok = true;
      for (int i = 0; i < 26; ++i) {
        if (cnt[i] > t[i]) {
          ok = false;
          break;
        }
      }
      if (ok) {
        ans.emplace_back(a);
      }
    }
    return ans;
  }
};

func wordSubsets(words1 []string, words2 []string) (ans []string) {
  cnt := [26]int{}
  for _, b := range words2 {
    t := [26]int{}
    for _, c := range b {
      t[c-'a']++
    }
    for i := range cnt {
      cnt[i] = max(cnt[i], t[i])
    }
  }
  for _, a := range words1 {
    t := [26]int{}
    for _, c := range a {
      t[c-'a']++
    }
    ok := true
    for i, v := range cnt {
      if v > t[i] {
        ok = false
        break
      }
    }
    if ok {
      ans = append(ans, a)
    }
  }
  return
}