Watch 9 video solutions for Report Spam Message, a medium level problem involving Array, Hash Table, String. This walkthrough by codi has 610 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1051 <= message[i].length, bannedWords[i].length <= 15message[i] and bannedWords[i] consist only of lowercase English letters.Problem Overview: You receive a message represented as an array of words and another list containing banned words. The task is to determine whether the message should be reported as spam. A message is considered spam if at least two words from the message appear in the banned list.
Approach 1: Hash Set for Fast Lookup (O(n + m) time, O(m) space)
The most practical solution converts the banned word list into a hash set. This gives constant-time membership checks. First iterate through the banned array and insert each word into the set. Then iterate through the message words and check whether each word exists in the set using a hash lookup. Maintain a counter for matches and stop once the count reaches two.
The key insight is that repeated membership checks become expensive if the banned list is scanned each time. A hash set reduces that lookup from O(m) to O(1). The total complexity becomes O(n + m), where n is the number of words in the message and m is the size of the banned list. Space complexity is O(m) for the set. This pattern appears frequently in problems involving fast membership checks on hash tables and word matching across arrays.
Approach 2: Frequency Count with Early Exit (O(n + m) time, O(m) space)
Another way is to track occurrences of banned words using a frequency structure. Build a hash map or set from the banned list, then iterate through the message while counting matches. As soon as the second banned word is encountered, immediately return true. This early exit avoids scanning the entire message when spam is detected early.
This approach behaves similarly to the hash set strategy but emphasizes counting and early termination. The algorithm still performs a single pass through the message with constant-time lookups. Time complexity remains O(n + m), and space complexity stays O(m). Early termination often improves real-world performance when spam appears near the beginning of the message.
Both solutions rely on efficient word comparison and are common in moderation or filtering systems where strings must be matched against restricted lists. Problems involving string matching and hash-based membership checks frequently use this exact design.
Recommended for interviews: The hash set lookup approach is what most interviewers expect. It demonstrates that you recognize repeated membership checks and optimize them with a hash-based structure. Mentioning the naive scan and then replacing it with a set shows clear reasoning. Implementing the early exit variant further shows attention to practical performance.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Set for Fast Lookup | O(n + m) | O(m) | General case where repeated membership checks are needed |
| Frequency Count with Early Exit | O(n + m) | O(m) | When spam may appear early and early termination improves runtime |