Skip to content

916. Word Subsets 👍

  • Time:
  • Space: 
 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
29
30
31
32
33
34
class Solution {
 public:
  vector<string> wordSubsets(vector<string>& A, vector<string>& B) {
    vector<string> ans;
    vector<int> countB(26);

    for (const string& b : B) {
      vector<int> temp = counter(b);
      for (int i = 0; i < 26; ++i)
        countB[i] = max(countB[i], temp[i]);
    }

    for (const string& a : A)
      if (isUniversal(counter(a), countB))
        ans.push_back(a);

    return ans;
  }

 private:
  vector<int> counter(const string& s) {
    vector<int> count(26);
    for (char c : s)
      ++count[c - 'a'];
    return count;
  }

  bool isUniversal(vector<int> countA, vector<int>& countB) {
    for (int i = 0; i < 26; ++i)
      if (countA[i] < countB[i])
        return false;
    return true;
  }
};

 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
29
30
31
32
class Solution {
  public List<String> wordSubsets(String[] A, String[] B) {
    List<String> ans = new ArrayList<>();
    int[] countB = new int[26];

    for (final String b : B) {
      int[] temp = counter(b);
      for (int i = 0; i < 26; ++i)
        countB[i] = Math.max(countB[i], temp[i]);
    }

    for (final String a : A)
      if (isUniversal(counter(a), countB))
        ans.add(a);

    return ans;
  }

  private int[] counter(final String s) {
    int[] count = new int[26];
    for (char c : s.toCharArray())
      ++count[c - 'a'];
    return count;
  }

  private boolean isUniversal(int[] countA, int[] countB) {
    for (int i = 0; i < 26; ++i)
      if (countA[i] < countB[i])
        return false;
    return true;
  }
}

1
2
3
4
5
6
7
8
class Solution:
  def wordSubsets(self, A: list[str], B: list[str]) -> list[str]:
    count = collections.Counter()

    for b in B:
      count = count | collections.Counter(b)

    return [a for a in A if collections.Counter(a) & count == count]