Today’s problem

https://leetcode.com/problems/word-subsets/

Intuition

The brute method would take $O(N^2\times (L+D))$ time, while $N$ is the length of the words, $L$ is the length of each word, and $D$ is the size of the dictionary (that is, 26 characters). However, $N \le 10^4$, which means that we cannot use brute method. Then we found out that we do not need to compare all $N$ words, instead, we only need to compare the maximum of the occurence of each characters in words2. For example, if ‘a’ appears 3 times in $words2[1]$, 2 times in $words2[2]$, 4 times in $words2[3]$, then ‘a’ must appears at least 4 times in a $words1[i]$ to add one to the answer. Therefore, all we need is to count the occurence of each character in word1, and count the maximun occurence of each character in every word2.

Approach

Count the occurence of each character in word1, and count the maximun occurence of each character in every word2.

Complexity

• Time complexity: $O(N \times (L + D))$, while $N$ is the length of the words, $L$ is the length of each word, and $D$ is the size of the dictionary (that is, 26 characters).

• Space complexity: $O(N \ times D)$.

Code

class Solution:
    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:
        wordcnt1, wordcnt2 = [], [0] * 26
        a = ord('a')
        for word in words1:
            cnt = [0] * 26
            for ch in word:
                x = ord(ch) - a
                cnt[x] += 1
            wordcnt1.append(cnt)
        
        for word in words2:
            cnt = [0] * 26
            for ch in word:
                x = ord(ch) - a
                cnt[x] += 1
            
            for j in range(26):
                wordcnt2[j] = max(wordcnt2[j], cnt[j])

        ans = []
        for i in range(len(words1)):
            flag = True
            for k in range(26):
                if wordcnt1[i][k] < wordcnt2[k]:
                    flag = False
                    break
            if flag:
                ans.append(words1[i])
        
        return ans