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

Example 3

Example 4

Example 5

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

Follow up