916. Word Subsets - Explanation

1. Brute Force

class Solution:
    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:
        res = []
        for w1 in words1:
            count1 = Counter(w1)
            is_subset = True

            for w2 in words2:
                count2 = Counter(w2)
                for c in count2:
                    if count2[c] > count1[c]:
                        is_subset = False
                        break

                if not is_subset: break

            if is_subset:
                res.append(w1)

        return res

Time & Space Complexity

Time complexity: $O(N * n + N * M * m)$
Space complexity:
- $O(1)$ extra space, since we have at most $26$ different characters.
- $O(N * n)$ space for the output list.

Where $N$ is the size of the array $words1$ , $n$ is the length of the longest word in $words1$ , $M$ is the size of the array $words2$ , and $m$ is the length of the longest word in $words2$ .

2. Greedy + Hash Map

class Solution:
    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:
        count_2 = defaultdict(int)
        for w in words2:
            count_w = Counter(w)
            for c, cnt in count_w.items():
                count_2[c] = max(count_2[c], cnt)

        res = []
        for w in words1:
            count_w = Counter(w)
            flag = True
            for c, cnt in count_2.items():
                if count_w[c] < cnt:
                    flag = False
                    break
            if flag:
                res.append(w)

        return res

Time & Space Complexity

Time complexity: $O(N * n + M * m)$
Space complexity:
- $O(1)$ extra space, since we have at most $26$ different characters.
- $O(N * n)$ space for the output list.

Where $N$ is the size of the array $words1$ , $n$ is the length of the longest word in $words1$ , $M$ is the size of the array $words2$ , and $m$ is the length of the longest word in $words2$ .