Search

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) 
   {
        int[] t = new int[26];
        for(String b : B) 
        {
            int[] tmp = new int[26];
            for(char c : b.toCharArray()) tmp[c - 'a']++;
            for(int i = 0; i < 26; i++) t[i] = Math.max(t[i], tmp[i]);
        }
        
        List<String> res = new ArrayList<>();  
        for(String a : A) if(isUniversal(a, t)) res.add(a);
        return res;
    }
    
    boolean isUniversal(String s, int[] t) 
    {
        int[] tmp = new int[26];
        for(char c : s.toCharArray()) tmp[c - 'a']++;
        for(int i = 0; i < 26; i++) if(tmp[i] < t[i]) return false;
        return true;
    }
}

16 views0 comments

Recent Posts

See All

A string s is called good if there are no two different characters in s that have the same frequency. Given a string s, return the minimum number of characters you need to delete to make s good. The f

The numeric value of a lowercase character is defined as its position (1-indexed) in the alphabet, so the numeric value of a is 1, the numeric value of b is 2, the numeric value of c is 3, and so on.