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. 举报垃圾信息

题目描述

解法

方法一：哈希表

评论