Word Subsets

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].

Solution:

class Solution {
    
    public List<String> wordSubsets(String[] A, String[] B) {
        Map<Character, Integer> map = new HashMap();
        for (int i = 0; i < B.length; i ++) {
            Map<Character, Integer> curr = new HashMap();
            for (char c : B[i].toCharArray()) {
                curr.put(c, curr.getOrDefault(c, 0) + 1);
                map.put(c, Math.max(map.getOrDefault(c, 0), curr.get(c)));
            }
        }
        List<String> result = new ArrayList();
        for (String s : A) {
            if (isSubset(s, map)) {
                result.add(s);
            }
        }
        return result;
    }
    
    private boolean isSubset(String a, Map<Character, Integer> mapB) {
        Map<Character, Integer> map = new HashMap();
        for (char c : a.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        for (Map.Entry<Character, Integer> entry : mapB.entrySet()) {
            char c = entry.getKey();
            if (map.get(c) == null || map.get(c) < entry.getValue()) {
                return false;
            }
        }
        return true;
    }
}