今日题目

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

解题思路

暴力解法的时间复杂度为 $O(N^2\times (L+D))$，其中 $N$ 为单词数组的长度，$L$ 为每个单词的长度，$D$ 为字符集大小（即 26 个字母）。 然而由于 $N \le 10^4$，暴力解法会超时。 进一步观察可以发现，我们无需逐一比较 words2 中的所有单词，只需统计 words2 中每个字符出现次数的最大值即可。 例如，若字符 ‘a’ 在 $words2[1]$ 中出现 3 次、在 $words2[2]$ 中出现 2 次、在 $words2[3]$ 中出现 4 次，那么 $words1[i]$ 中 ‘a’ 至少需要出现 4 次，才能被计入答案。 因此，我们只需统计 words1 中每个单词各字符的出现次数，以及 words2 中每个字符出现次数的最大值，再逐一比较即可。

算法步骤

统计 words1 中每个单词各字符的出现次数，以及 words2 中每个字符出现次数的最大值，然后逐一比较判断是否满足条件。

复杂度分析

  • 时间复杂度：$O(N \times (L + D))$，其中 $N$ 为单词数组的长度，$L$ 为每个单词的长度，$D$ 为字符集大小（即 26 个字母）。

  • 空间复杂度：$O(N \times D)$。

代码

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