916. Word Subsets

Description

You are given two string arrays words1 and words2.

A string b is a subset of string 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".

A string a from words1 is universal if for every string b in words2, b is a subset of a.

Return an array of all the universal strings in words1. You may return the answer in any order.

 

Example 1:

Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]

Output: ["facebook","google","leetcode"]

Example 2:

Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["lc","eo"]

Output: ["leetcode"]

Example 3:

Input: words1 = ["acaac","cccbb","aacbb","caacc","bcbbb"], words2 = ["c","cc","b"]

Output: ["cccbb"]

 

Constraints:

• 1 <= words1.length, words2.length <= 104
• 1 <= words1[i].length, words2[i].length <= 10
• words1[i] and words2[i] consist only of lowercase English letters.
• All the strings of words1 are unique.

Solutions

Solution 1: Counting

Traverse each word b in words2, count the maximum occurrence of each letter, and record it as cnt.

Then traverse each word a in words1, count the occurrence of each letter, and record it as t. If the occurrence of each letter in cnt is not greater than the occurrence in t, then a is a universal word, and add it to the answer.

The time complexity is $O(L)$, where $L$ is the sum of the lengths of all words in words1 and words2.

Python3JavaC++Go

class Solution:
    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:
        cnt = Counter()
        for b in words2:
            t = Counter(b)
            for c, v in t.items():
                cnt[c] = max(cnt[c], v)
        ans = []
        for a in words1:
            t = Counter(a)
            if all(v <= t[c] for c, v in cnt.items()):
                ans.append(a)
        return ans

class Solution {
    public List<String> wordSubsets(String[] words1, String[] words2) {
        int[] cnt = new int[26];
        for (var b : words2) {
            int[] t = new int[26];
            for (int i = 0; i < b.length(); ++i) {
                t[b.charAt(i) - 'a']++;
            }
            for (int i = 0; i < 26; ++i) {
                cnt[i] = Math.max(cnt[i], t[i]);
            }
        }
        List<String> ans = new ArrayList<>();
        for (var a : words1) {
            int[] t = new int[26];
            for (int i = 0; i < a.length(); ++i) {
                t[a.charAt(i) - 'a']++;
            }
            boolean ok = true;
            for (int i = 0; i < 26; ++i) {
                if (cnt[i] > t[i]) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                ans.add(a);
            }
        }
        return ans;
    }
}

class Solution {
public:
    vector<string> wordSubsets(vector<string>& words1, vector<string>& words2) {
        int cnt[26] = {0};
        int t[26];
        for (auto& b : words2) {
            memset(t, 0, sizeof t);
            for (auto& c : b) {
                t[c - 'a']++;
            }
            for (int i = 0; i < 26; ++i) {
                cnt[i] = max(cnt[i], t[i]);
            }
        }
        vector<string> ans;
        for (auto& a : words1) {
            memset(t, 0, sizeof t);
            for (auto& c : a) {
                t[c - 'a']++;
            }
            bool ok = true;
            for (int i = 0; i < 26; ++i) {
                if (cnt[i] > t[i]) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                ans.emplace_back(a);
            }
        }
        return ans;
    }
};

func wordSubsets(words1 []string, words2 []string) (ans []string) {
    cnt := [26]int{}
    for _, b := range words2 {
        t := [26]int{}
        for _, c := range b {
            t[c-'a']++
        }
        for i := range cnt {
            cnt[i] = max(cnt[i], t[i])
        }
    }
    for _, a := range words1 {
        t := [26]int{}
        for _, c := range a {
            t[c-'a']++
        }
        ok := true
        for i, v := range cnt {
            if v > t[i] {
                ok = false
                break
            }
        }
        if ok {
            ans = append(ans, a)
        }
    }
    return
}

Comments