916. Word Subsets

Description

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.

Constraints

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

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */
 
 class Solution {
    
    public List<String> wordSubsets(String[] A, String[] B) {
                
        int[] count = new int[26];
        
        for(String b: B) {
            Map<Character, Integer> map = new HashMap();
            
            for(char ch: b.toCharArray()) {
                map.put(ch, map.getOrDefault(ch, 0) + 1);
                count[ch-'a'] = Math.max(count[ch-'a'], map.get(ch));
            }
        }
        
        List<String> wordList = new ArrayList();
        
        for(String a: A) {
            Map<Character, Integer> map = new HashMap();
            for(char ch: a.toCharArray()) {
                map.put(ch, map.getOrDefault(ch, 0) + 1);
            }
            
            boolean isValid = true;
            for(char ch = 'a'; ch <= 'z'; ch++) {
                if(count[ch-'a'] > 0 && 
                    (!map.containsKey(ch) || map.get(ch) < count[ch-'a'])) {
                    isValid = false;
                    break;
                }
            }
            
            if(isValid) {
                wordList.add(a);
            }
        }
        
        return wordList;
    }
}

Solution 2

/**
 * Time complexity : O(A+B), where A and B is the total amount of information 
 *    in A and B respectively.
 * Space complexity : O(A.length+B.length).
 */

class Solution {
    public List<String> wordSubsets(String[] A, String[] B) {
        int[] bmax = count("");
        for (String b: B) {
            int[] bCount = count(b);
            for (int i = 0; i < 26; ++i) {
                bmax[i] = Math.max(bmax[i], bCount[i]);
            }
        }

        List<String> ans = new ArrayList();
        
        for (String a: A) {
            int[] aCount = count(a);
            boolean isValid = true;
            for (int i = 0; i < 26; ++i) {
                if (aCount[i] < bmax[i]) {
                    isValid = false;
                    break;
                }
            }
            if(isValid) {
                ans.add(a);
            }
        }

        return ans;
    }

    public int[] count(String str) {
        int[] ans = new int[26];
        for (char c: str.toCharArray())
            ans[c - 'a']++;
        return ans;
    }
}

Follow up