Skip to content

3295. Report Spam Message

Description

You are given an array of strings message and an array of strings bannedWords.

An array of words is considered spam if there are at least two words in it that exactly match any word in bannedWords.

Return true if the array message is spam, and false otherwise.

 

Example 1:

Input: message = ["hello","world","leetcode"], bannedWords = ["world","hello"]

Output: true

Explanation:

The words "hello" and "world" from the message array both appear in the bannedWords array.

Example 2:

Input: message = ["hello","programming","fun"], bannedWords = ["world","programming","leetcode"]

Output: false

Explanation:

Only one word from the message array ("programming") appears in the bannedWords array.

 

Constraints:

  • 1 <= message.length, bannedWords.length <= 105
  • 1 <= message[i].length, bannedWords[i].length <= 15
  • message[i] and bannedWords[i] consist only of lowercase English letters.

Solutions

Solution 1: Hash Table

Thinking

A message is spam if at least two words lie in the banned list. \(n,m\le 10^5\), so scanning the banned list per word is quadratic.

Put banned words in a hash set and count hits in the message; return whether the count is at least \(2\). Expected linear time.

We use a hash table \(s\) to store all the words in \(\textit{bannedWords}\). Then, we traverse each word in \(\textit{message}\). If the word appears in the hash table \(s\), we increment the counter \(cnt\) by one. If \(cnt\) is greater than or equal to \(2\), we return \(\text{true}\); otherwise, we return \(\text{false}\).

The time complexity is \(O((n + m) \times |w|)\), and the space complexity is \(O(m \times |w|)\). Here, \(n\) is the length of the array \(\textit{message}\), and \(m\) and \(|w|\) are the length of the array \(\textit{bannedWords}\) and the maximum length of the words in the array, respectively.

1
2
3
4
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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;
}

Comments