[LeetCode] Problem 916 - Word Subsets

Posted on | In ,

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

No.1

Input: A = [“amazon”,”apple”,”facebook”,”google”,”leetcode”], B = [“e”,”o”]

Output: [“facebook”,”google”,”leetcode”]

No.2

Input: A = [“amazon”,”apple”,”facebook”,”google”,”leetcode”], B = [“l”,”e”]

Output: [“apple”,”google”,”leetcode”]

No.3

Input: A = [“amazon”,”apple”,”facebook”,”google”,”leetcode”], B = [“e”,”oo”]

Output: [“facebook”,”google”]

No.4

Input: A = [“amazon”,”apple”,”facebook”,”google”,”leetcode”], B = [“lo”,”eo”]

Output: [“google”,”leetcode”]

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public List<String> wordSubsets(String[] A, String[] B) {
    List<String> result = new ArrayList<>();
    int[] maxCount = new int[26];

    for (String b : B) {
        int[] count = count(b);

        for (int i = 0; i < 26; i++)
            maxCount[i] = Math.max(maxCount[i], count[i]);
    }

    for (String a : A) {
        int[] count = count(a);
        boolean isSubset = true;

        for (int i = 0; i < 26; i++) {
            if (count[i] < maxCount[i]) {
                isSubset = false;
                break;
            }
        }

        if (isSubset)
            result.add(a);
    }

    return result;
}

private int[] count(String str) {
    int[] count = new int[26];

    for (int i = 0; i < str.length(); i++) {
        int idx = str.charAt(i) - 'a';
        count[idx]++;
    }

    return count;
}