Formatted question description: https://leetcode.ca/all/916.html

916. Word Subsets (Medium)

We are given two arrays A and B of words.  Each word is a string of lowercase letters.

Now, say that word b is a subset of word 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".

Now say a word a from A is universal if for every b in B, b is a subset of a. 

Return a list of all universal words in A.  You can return the words in any order.

 

Example 1:

Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["e","o"]
Output: ["facebook","google","leetcode"]

Example 2:

Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["l","e"]
Output: ["apple","google","leetcode"]

Example 3:

Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["e","oo"]
Output: ["facebook","google"]

Example 4:

Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["lo","eo"]
Output: ["google","leetcode"]

Example 5:

Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["ec","oc","ceo"]
Output: ["facebook","leetcode"]

 

Note:

1. 1 <= A.length, B.length <= 10000
2. 1 <= A[i].length, B[i].length <= 10
3. A[i] and B[i] consist only of lowercase letters.
4. All words in A[i] are unique: there isn't i != j with A[i] == A[j].

Related Topics:
String

Solution 1.

// OJ: https://leetcode.com/problems/word-subsets/
// Time: O((A + B) * N) where N is the maximum length of string
// Space: O(1)
class Solution {
public:
    vector<string> wordSubsets(vector<string>& A, vector<string>& B) {
        int N = A.size(), target[26] = {}, j = 0;
        for (auto &b : B) {
            int cnt[26] = {};
            for (char c : b) cnt[c - 'a']++;
            for (int i = 0; i < 26; ++i) target[i] = max(target[i], cnt[i]);
        }
        for (int i = 0; i < N; ++i) {
            int cnt[26] = {};
            for (char c : A[i]) cnt[c - 'a']++;
            bool valid = true;
            for (int k = 0; k < 26 && valid; ++k) valid = target[k] <= cnt[k];
            if (valid) A[j++] = A[i];
        }
        A.resize(j);
        return A;
    }
};

Java

• Java
• C++
• Python

• class Solution {
      public List<String> wordSubsets(String[] A, String[] B) {
          List<String> universalList = new ArrayList<String>();
          int[] counts = getMaxCounts(B);
          for (String word : A) {
              int[] wordCounts = getWordCounts(word);
              boolean flag = true;
              for (int i = 0; i < 26; i++) {
                  if (wordCounts[i] < counts[i]) {
                      flag = false;
                      break;
                  }
              }
              if (flag)
                  universalList.add(word);
          }
          return universalList;
      }
  
      public int[] getMaxCounts(String[] array) {
          int[] counts = new int[26];
          for (String word : array) {
              int[] curCounts = new int[26];
              char[] wordArray = word.toCharArray();
              for (char c : wordArray)
                  curCounts[c - 'a']++;
              for (int i = 0; i < 26; i++)
                  counts[i] = Math.max(counts[i], curCounts[i]);
          }
          return counts;
      }
  
      public int[] getWordCounts(String word) {
          int[] wordCounts = new int[26];
          char[] wordArray = word.toCharArray();
          for (char c : wordArray)
              wordCounts[c - 'a']++;
          return wordCounts;
      }
  }
  

• // OJ: https://leetcode.com/problems/word-subsets/
  // Time: O((A + B) * N) where N is the maximum length of string
  // Space: O(1)
  class Solution {
  public:
      vector<string> wordSubsets(vector<string>& A, vector<string>& B) {
          int N = A.size(), target[26] = {}, j = 0;
          for (auto &b : B) {
              int cnt[26] = {};
              for (char c : b) cnt[c - 'a']++;
              for (int i = 0; i < 26; ++i) target[i] = max(target[i], cnt[i]);
          }
          for (int i = 0; i < N; ++i) {
              int cnt[26] = {};
              for (char c : A[i]) cnt[c - 'a']++;
              bool valid = true;
              for (int k = 0; k < 26 && valid; ++k) valid = target[k] <= cnt[k];
              if (valid) A[j++] = A[i];
          }
          A.resize(j);
          return A;
      }
  };
  

• class Solution(object):
      def wordSubsets(self, A, B):
          """
          :type A: List[str]
          :type B: List[str]
          :rtype: List[str]
          """
          B = set(B)
          res = []
          count = collections.defaultdict(int)
          for b in B:
              cb = collections.Counter(b)
              for c, v in cb.items():
                  count[c] = max(count[c], v)
          res = []
          for a in A:
              ca = collections.Counter(a)
              isSuccess = True
              for c, v in count.items():
                  if v > ca[c]:
                      isSuccess = False
                      break
              if isSuccess:
                  res.append(a)
          return res
  

All Problems

All Solutions