952. Word Subsets¶

LeetCode Problem View on GitHub

952. Word Subsets

Medium

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 = ["l","e"]
Output: ["apple","google","leetcode"]

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.

Solution¶

class Solution {
    public List<String> wordSubsets(String[] words1, String[] words2) {
        int n = words1.length, m = words2.length;
        int freq[] = new int[26];
        for (int i = 0; i < m; i++) {
            int temp_freq[] = new int[26];
            for (int j = 0; j < words2[i].length(); j++) temp_freq[words2[i].charAt(j) - 'a']++;
            for (int j = 0; j < 26; j++) freq[j] = Math.max(freq[j], temp_freq[j]);
        }
        int vis[] = new int[n];
        for (int i = 0; i < n; i++) {
            int temp_freq[] = new int[26];
            for (int j = 0; j < words1[i].length(); j++) temp_freq[words1[i].charAt(j) - 'a']++;
            for (int j = 0; j < 26; j++) if (temp_freq[j] < freq[j]) vis[i] = 1;
        }
        List<String> res = new ArrayList<>();
        for (int i = 0; i < n; i++) if (vis[i] == 0) res.add(words1[i]);
        return res;
    }
}

Complexity Analysis¶

• Time Complexity: O(?)
• Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here