Medium

题目描述

给你两个字符串数组 words1 和 words2。

如果字符串 b 中的每个字母在字符串 a 中都出现了（包括重复次数），那么称字符串 b 是字符串 a 的子集。

  • 例如，"wrr" 是 "warrior" 的子集，但不是 "world" 的子集。

如果对于 words2 中的每一个字符串 b，字符串 a 都包含 b，那么我们称 words1 中的字符串 a 是通用的。

以数组形式返回 words1 中所有的通用字符串。你可以按任意顺序返回答案。

示例 1：

输入：words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]
输出：["facebook","google","leetcode"]

示例 2：

输入：words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["lc","eo"]
输出：["leetcode"]

示例 3：

输入：words1 = ["acaac","cccbb","aacbb","caacc","bcbbb"], words2 = ["c","cc","b"]
输出：["cccbb"]

提示：

  • 1 <= words1.length, words2.length <= 10^4
  • 1 <= words1[i].length, words2[i].length <= 10
  • words1[i] 和 words2[i] 仅由小写英文字母组成
  • words1 中的所有字符串互不相同

解题思路

这道题的核心思想是将 words2 中的所有约束条件合并成一个"最大需求"，然后检查 words1 中的每个单词是否能满足这个需求。

解题思路：

  1. 合并约束条件：遍历 words2 中的所有字符串，统计每个字符在所有字符串中出现的最大次数。例如，如果 words2 = ["c", "cc", "b"]，那么字符 'c' 的最大需求是 2 次，字符 'b' 的最大需求是 1 次。

  2. 检查每个候选字符串：对于 words1 中的每个字符串，统计其字符频次，然后检查是否满足步骤1中得到的最大需求。

  3. 具体实现：

    • 使用哈希表或数组统计字符频次
    • 对于每个字符，如果候选字符串中该字符的出现次数小于最大需求，则该字符串不是通用的

优化点： 通过预先合并所有约束条件，避免了对每个 words1 中的字符串都要检查所有 words2 中的字符串，大大提高了效率。

时间复杂度： O(M + N)，其中 M 是所有 words1 字符串的字符总数，N 是所有 words2 字符串的字符总数。

代码实现

class Solution {
public:
    vector<string> wordSubsets(vector<string>& words1, vector<string>& words2) {
        // 统计words2中每个字符的最大需求
        vector<int> maxReq(26, 0);
        for (const string& word : words2) {
            vector<int> count(26, 0);
            for (char c : word) {
                count[c - 'a']++;
            }
            for (int i = 0; i < 26; i++) {
                maxReq[i] = max(maxReq[i], count[i]);
            }
        }
        
        vector<string> result;
        for (const string& word : words1) {
            vector<int> count(26, 0);
            for (char c : word) {
                count[c - 'a']++;
            }
            
            bool isUniversal = true;
            for (int i = 0; i < 26; i++) {
                if (count[i] < maxReq[i]) {
                    isUniversal = false;
                    break;
                }
            }
            
            if (isUniversal) {
                result.push_back(word);
            }
        }
        
        return result;
    }
};

class Solution:
    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:
        # 统计words2中每个字符的最大需求
        max_req = {}
        for word in words2:
            count = {}
            for c in word:
                count[c] = count.get(c, 0) + 1
            for c, freq in count.items():
                max_req[c] = max(max_req.get(c, 0), freq)
        
        result = []
        for word in words1:
            count = {}
            for c in word:
                count[c] = count.get(c, 0) + 1
            
            is_universal = True
            for c, req in max_req.items():
                if count.get(c, 0) < req:
                    is_universal = False
                    break
            
            if is_universal:
                result.append(word)
        
        return result

public class Solution {
    public IList<string> WordSubsets(string[] words1, string[] words2) {
        // 统计words2中每个字符的最大需求
        int[] maxReq = new int[26];
        foreach (string word in words2) {
            int[] count = new int[26];
            foreach (char c in word) {
                count[c - 'a']++;
            }
            for (int i = 0; i < 26; i++) {
                maxReq[i] = Math.Max(maxReq[i], count[i]);
            }
        }
        
        List<string> result = new List<string>();
        foreach (string word in words1) {
            int[] count = new int[26];
            foreach (char c in word) {
                count[c - 'a']++;
            }
            
            bool isUniversal = true;
            for (int i = 0; i < 26; i++) {
                if (count[i] < maxReq[i]) {
                    isUniversal = false;
                    break;
                }
            }
            
            if (isUniversal) {
                result.Add(word);
            }
        }
        
        return result;
    }
}

var wordSubsets = function(words1, words2) {
    // 统计words2中每个字符的最大需求
    const maxReq = new Array(26).fill(0);
    for (const word of words2) {
        const count = new Array(26).fill(0);
        for (const c of word) {
            count[c.charCodeAt(0) - 97]++;
        }
        for (let i = 0; i < 26; i++) {
            maxReq[i] = Math.max(maxReq[i], count[i]);
        }
    }
    
    const result = [];
    for (const word of words1) {
        const count = new Array(26).fill(0);
        for (const c of word) {
            count[c.charCodeAt(0) - 97]++;
        }
        
        let isUniversal = true;
        for (let i = 0; i < 26; i++) {
            if (count[i] < maxReq[i]) {
                isUniversal = false;
                break;
            }
        }
        
        if (isUniversal) {
            result.push(word);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(M + N)M 是所有 words1 字符串的字符总数，N 是所有 words2 字符串的字符总数
空间复杂度O(1)使用固定大小的数组存储字符频次（26个字母）