Problem 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.

Intuition

The problem requires determining if a message contains at least two occurrences of words that are present in the bannedWords list. To achieve this efficiently, we utilize a hash table (implemented as a set in Python) to store the words from bannedWords. This allows for O(1) average time complexity for checking the presence of words from message in the bannedWords.

The solution involves iterating through each word in the message and checking if it exists in the banned words set. By maintaining a count of how many words from message are found in this set, we can ascertain if the message contains enough banned words to be classified as spam. If the count reaches two or more during this iteration, the message is deemed spam, and we return true. Otherwise, we conclude that it is not spam and return false.

Solution Approach

The solution employs a hash table to efficiently check for the presence of banned words in the message. The key steps in the approach are as follows:

1. Initialize the Data Structure:

   • Convert the bannedWords list into a set s. This conversion leverages the set's property of average O(1) time complexity for membership checks, making it ideal for this task.

2. Iterate Through the Message:

   • Traverse each word in the message array.
   • For each word, use the set membership operation to check if it exists in the set s. Specifically, w in s will return True if the word w from message is in the bannedWords set.

3. Count and Decision:

   • Count the number of words in message that appear in the set s. This is accomplished using a generator expression within the sum function: sum(w in s for w in message).
   • Compare this count against the threshold of 2. If the count is greater than or equal to 2, return True indicating the message is spam. Otherwise, return False.

The code implementation encapsulating this logic is succinctly represented by:

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

The approach efficiently determines if a message should be classified as spam by leveraging the properties of sets for fast lookup, thereby ensuring the solution is optimal.

Example Walkthrough

Let's consider a small example to illustrate the solution approach:

Suppose we have the following arrays:

• message: ["free", "win", "prize", "money", "win"]
• bannedWords: ["win", "free", "offer"]

Our objective is to determine if the message should be considered spam by checking if it has at least two words matching those in bannedWords.

1. Initialize the Data Structure:

   • Convert bannedWords into a set s: s = {"win", "free", "offer"}.

2. Iterate Through the Message:

   • Traverse each word in the message. For each word, check if it exists in set s:
     • "free" → present in s (count=1)
     • "win" → present in s (count=2)
     • "prize" → not in s
     • "money" → not in s
     • "win" → present in s

3. Count and Decision:

   • Count the number of words from message present in s. In our case, this count is 3, which exceeds the threshold of 2.
   • Since the count is greater than or equal to 2, the function will return True, indicating the message is spam.

The above example demonstrates the solution's efficiency in determining spam status by utilizing set membership checks, ultimately classifying the message as spam.

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(n * m * |w|). This is because for each word in the message list of length n, we check for its presence in the set s, which contains m banned words. Each of these checks (in the worst-case) involves comparing words, which might entail examining all characters of maximum length |w|.

The space complexity is O(m * |w|). This arises from storing the bannedWords in a set, where m is the number of banned words and |w| is the maximum length of these words.

Learn more about how to find time and space complexity quickly.