916. Word Subsets #

Problem #

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

Problem Summary #

We are given two word arrays A and B. Each word is a string of lowercase letters. Now, if every letter in b appears in a, including repeated letters, then word b is called a subset of word a. For example, “wrr” is a subset of “warrior”, but not a subset of “world”. If for every word b in B, b is a subset of a, then we call word a in A universal. You can return all universal words in A as a list in any order.

Solution Approach #

• Easy problem. First count the frequency of each letter needed by the words in array B, then check each word in array A one by one to see whether it meets these frequencies. If it does, output it.

Code #

package leetcode

func wordSubsets(A []string, B []string) []string {
	var counter [26]int
	for _, b := range B {
		var m [26]int
		for _, c := range b {
			j := c - 'a'
			m[j]++
		}
		for i := 0; i < 26; i++ {
			if m[i] > counter[i] {
				counter[i] = m[i]
			}
		}
	}
	var res []string
	for _, a := range A {
		var m [26]int
		for _, c := range a {
			j := c - 'a'
			m[j]++
		}
		ok := true
		for i := 0; i < 26; i++ {
			if m[i] < counter[i] {
				ok = false
				break
			}
		}
		if ok {
			res = append(res, a)
		}
	}
	return res
}