916 - Word Subsets

You are given two string arrays words1 and words2.

A string b is a subset of string a if every letter in b occurs in a including multiplicity.

• For example, "wrr" is a subset of "warrior" but is not a subset of "world".

A string a from words1 is universal if for every string b in words2, b is a subset of a.

Return an array of all the universal strings in words1. You may return the answer in any order.

 Example 1:

Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]
Output: ["facebook","google","leetcode"]

Example 2:

Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["l","e"]
Output: ["apple","google","leetcode"]

 Constraints:

• 1 <= words1.length, words2.length <= 104
• 1 <= words1[i].length, words2[i].length <= 10
• words1[i] and words2[i] consist only of lowercase English letters.
• All the strings of words1 are unique.

C++

• 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;
      }
  };

JAVA

• 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;
      }
  }

PYTHON

• class Solution:
      def wordSubsets(self, words1: list, words2: list) -> list:
          from collections import Counter
          cnt = Counter()
          for b in words2:
              cnt |= Counter(b)
          ans = []
          for a in words1:
              if not cnt - Counter(a):
                  ans.append(a)
          return ans