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]
andbannedWords[i]
consist only of lowercase English letters.
Solutions
Solution 1: Hash Table
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 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 |
|