3295. 举报垃圾信息

题目描述

给你一个字符串数组 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⁵
1 <= message[i].length, bannedWords[i].length <= 15
message[i] 和 bannedWords[i] 都只由小写英文字母组成。

解法

方法一：哈希表

我们用一个哈希表 \(s\) 存储 \(\textit{bannedWords}\) 中的所有单词，然后遍历 \(\textit{message}\) 中的每个单词，如果单词在哈希表 \(s\) 中出现，我们就将计数器 \(cnt\) 加一，如果 \(cnt\) 大于等于 \(2\)，我们就返回 \(\text{true}\)，否则返回 \(\text{false}\)。

时间复杂度 \(O((n + m) \times |w|)\)，空间复杂度 \(O(m \times |w|)\)。其中 \(n\) 是数组 \(\textit{message}\) 的长度，而 \(m\) 和 \(|w|\) 分别是数组 \(\textit{bannedWords}\) 的长度和数组中单词的最大长度。

Python3JavaC++GoTypeScript

class Solution:
    def reportSpam(self, message: List[str], bannedWords: List[str]) -> bool:
        s = set(bannedWords)
        return sum(w in s for w in message) >= 2

class Solution {
    public boolean reportSpam(String[] message, String[] bannedWords) {
        Set<String> s = new HashSet<>();
        for (var w : bannedWords) {
            s.add(w);
        }
        int cnt = 0;
        for (var w : message) {
            if (s.contains(w) && ++cnt >= 2) {
                return true;
            }
        }
        return false;
    }
}

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

func reportSpam(message []string, bannedWords []string) bool {
    s := map[string]bool{}
    for _, w := range bannedWords {
        s[w] = true
    }
    cnt := 0
    for _, w := range message {
        if s[w] {
            cnt++
            if cnt >= 2 {
                return true
            }
        }
    }
    return false
}

function reportSpam(message: string[], bannedWords: string[]): boolean {
    const s = new Set<string>(bannedWords);
    let cnt = 0;
    for (const w of message) {
        if (s.has(w) && ++cnt >= 2) {
            return true;
        }
    }
    return false;
}

3295. 举报垃圾信息

题目描述

解法

方法一：哈希表

评论