题目描述

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

如果数组中 至少 存在两个单词与 bannedWords 中的任一单词 完全相同，则该数组被视为 垃圾信息。

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

样例

输入：
message = ["hello","world","leetcode"]
bannedWords = ["world","hello"]

输出：true

解释：

数组 message 中的 "hello" 和 "world" 都出现在数组 bannedWords 中。

输入：
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] 都只由小写英文字母组成。

算法

(哈希表) $O((n + m)L)$

1. 将 bannedWords 存入哈希表中，然后遍历 message 每个单词，判断是否在哈希表中出现过。

时间复杂度

• 预处理哈希表的时间复杂度为 $O(mL)$。
• 判断单词是否在哈希表中出现过的时间复杂度为 $O(nL)$。
• 故总时间复杂度为 $O((n + m)L)$。

空间复杂度

• 需要 $O(mL)$ 的额外空间存储哈希表。

C++ 代码

class Solution {
public:
    bool reportSpam(vector<string>& message, vector<string>& bannedWords) {
        unordered_set<string> seen(bannedWords.begin(), bannedWords.end());

        int cnt = 0;
        for (const auto &s : message) {
            if (seen.count(s))
                ++cnt;

            if (cnt == 2)
                return true;
        }

        return false;
    }
};