Medium

题目描述

给你一个字符串数组 message 和一个字符串数组 bannedWords。

如果一个单词数组中至少有两个单词与 bannedWords 中的任何单词完全匹配，则认为该数组是垃圾信息。

如果数组 message 是垃圾信息，返回 true，否则返回 false。

示例 1：

输入：message = ["hello","world","leetcode"], bannedWords = ["world","hello"]
输出：true
解释：
message 数组中的单词 "hello" 和 "world" 都出现在 bannedWords 数组中。

示例 2：

输入：message = ["hello","programming","fun"], bannedWords = ["world","programming","leetcode"]
输出：false
解释：
message 数组中只有一个单词（"programming"）出现在 bannedWords 数组中。

约束条件：

  • 1 <= message.length, bannedWords.length <= 10^5
  • 1 <= message[i].length, bannedWords[i].length <= 15
  • message[i] 和 bannedWords[i] 只包含小写英文字母。

提示：

  • 使用哈希集合。

解题思路

这道题的核心是判断 message 中是否至少有两个单词出现在 bannedWords 中。

解题思路：

  1. 哈希集合优化查找：将 bannedWords 转换为哈希集合，这样可以在 O(1) 时间内判断一个单词是否为禁用词。

  2. 计数匹配单词：遍历 message 中的每个单词，如果该单词在禁用词集合中，就将匹配计数加1。

  3. 提前返回：一旦找到至少2个匹配的单词，立即返回 true，避免不必要的继续遍历。

  4. 最终判断：如果遍历完所有单词后匹配数少于2个，返回 false。

时间复杂度分析：

  • 构建哈希集合：O(B)，其中 B 是 bannedWords 的长度
  • 遍历 message：O(M)，其中 M 是 message 的长度
  • 总体时间复杂度：O(M + B)

空间复杂度：

  • 哈希集合存储禁用词：O(B)

这种方法比暴力的双重循环（O(M×B)）要高效得多，特别是在数据量较大时优势明显。

代码实现

class Solution {
public:
    bool reportSpam(vector<string>& message, vector<string>& bannedWords) {
        unordered_set<string> bannedSet(bannedWords.begin(), bannedWords.end());
        int count = 0;
        
        for (const string& word : message) {
            if (bannedSet.count(word)) {
                count++;
                if (count >= 2) {
                    return true;
                }
            }
        }
        
        return false;
    }
};

class Solution:
    def reportSpam(self, message: List[str], bannedWords: List[str]) -> bool:
        banned_set = set(bannedWords)
        count = 0
        
        for word in message:
            if word in banned_set:
                count += 1
                if count >= 2:
                    return True
        
        return False

public class Solution {
    public bool ReportSpam(string[] message, string[] bannedWords) {
        HashSet<string> bannedSet = new HashSet<string>(bannedWords);
        int count = 0;
        
        foreach (string word in message) {
            if (bannedSet.Contains(word)) {
                count++;
                if (count >= 2) {
                    return true;
                }
            }
        }
        
        return false;
    }
}

var reportSpam = function(message, bannedWords) {
    const bannedSet = new Set(bannedWords);
    let count = 0;
    
    for (const word of message) {
        if (bannedSet.has(word)) {
            count++;
            if (count >= 2) {
                return true;
            }
        }
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(M + B)，其中 M 是 message 的长度，B 是 bannedWords 的长度
空间复杂度O(B)，用于存储禁用词的哈希集合