Report Spam Message
MedPrompt
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]andbannedWords[i]consist only of lowercase English letters.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly translates the problem statement into code. We iterate through each word in the message and, for each word, we iterate through the entire bannedWords array to check for a match. A counter keeps track of how many banned words have been found in the message.
Algorithm
- Initialize a counter,
bannedCount, to zero. - Iterate through each
wordin themessagearray. - For each
word, start a nested loop to iterate through everybannedWordin thebannedWordsarray. - Inside the nested loop, compare the current
wordfrom the message with the currentbannedWord. - If they are an exact match, increment
bannedCountand break the inner loop to move to the next word inmessage. - After the inner loop, check if
bannedCounthas reached 2. If it has, the condition for spam is met, so returntrueimmediately. - If the outer loop finishes and
bannedCountis less than 2, returnfalse.
Walkthrough
This method involves a straightforward, nested-loop comparison. We take each word from the message and compare it against every single word in the bannedWords list. We use a counter to track the number of matches found. If the count of banned words found in the message reaches two, we can immediately conclude the message is spam and return true. If we iterate through the entire message without the count reaching two, the message is not spam.
class Solution { public boolean isSpam(String[] message, String[] bannedWords) { int bannedCount = 0; for (String word : message) { for (String bannedWord : bannedWords) { if (word.equals(bannedWord)) { bannedCount++; // Once a word is identified as banned, // we can break the inner loop and check the next word in the message. break; } } // Early exit if we've already found two banned words. if (bannedCount >= 2) { return true; } } return false; }}Complexity
Time
O(N * M * L), where N is the number of words in `message`, M is the number of words in `bannedWords`, and L is the maximum length of a word. For each of the N words in `message`, we iterate through all M words in `bannedWords`. String comparison takes O(L) time. This approach is too slow for the given constraints.
Space
O(1), as we only use a few variables to store the count and loop indices, not dependent on the input size.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space, making it very memory-efficient.
Cons
Extremely inefficient for large inputs due to the O(N*M) complexity of the nested loops.
Will likely cause a 'Time Limit Exceeded' (TLE) error on platforms with strict time constraints.
To improve upon the brute-force approach, we can optimize the process of checking if a word is banned. Instead of repeatedly scanning the bannedWords array, we can first store all banned words in a data structure that provides fast lookups, such as a Hash Set. This pre-processing step allows us to check if a word is banned in nearly constant time on average.
Algorithm
- Create a
HashSet<String>to store the banned words for efficient lookup. - Iterate through the
bannedWordsarray and add every word to the hash set. - Initialize a counter
bannedCountto 0. - Iterate through each
wordin themessagearray. - For each
word, use the hash set'scontainsmethod to check if it is a banned word. - If the word is found in the set, increment
bannedCount. - If
bannedCountreaches 2, we have found at least two banned words. Returntrueimmediately. - If the loop completes and
bannedCountis still less than 2, returnfalse.
Walkthrough
This optimized solution avoids the costly repeated search through the bannedWords array. By first populating a HashSet with all the banned words, we create a quick-reference dictionary. Checking if a word is in this set is, on average, a constant-time operation. We then iterate through the message just once, checking each word against our set. We keep a count of the banned words found, and as soon as the count hits two, we return true. This pre-computation step dramatically reduces the overall time complexity.
import java.util.HashSet;import java.util.Set;import java.util.Arrays; class Solution { public boolean isSpam(String[] message, String[] bannedWords) { // Step 1: Add all banned words to a HashSet for O(1) average time lookups. Set<String> bannedSet = new HashSet<>(Arrays.asList(bannedWords)); // Step 2: Iterate through the message and count banned words. int bannedCount = 0; for (String word : message) { if (bannedSet.contains(word)) { bannedCount++; } // Step 3: If the count reaches 2, it's spam. Return true immediately. if (bannedCount >= 2) { return true; } } // If the loop finishes, the message is not spam. return false; }}Complexity
Time
O((N + M) * L), where N is the length of `message`, M is the length of `bannedWords`, and L is the maximum word length. It takes O(M * L) to build the hash set and O(N * L) to iterate through the message and perform lookups. This is efficient enough to pass the given constraints.
Space
O(M * L), where M is the number of words in `bannedWords` and L is their maximum length. This space is required to store the banned words in the hash set.
Trade-offs
Pros
Highly efficient time complexity, suitable for large inputs.
The standard and most practical solution for this type of 'existence check' problem.
Cons
Uses extra space proportional to the number and length of banned words.
Solutions
Solution
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 ; } }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 ; } };class Solution : def reportSpam ( self , message : List [ str ], bannedWords : List [ str ]) -> bool : s = set ( bannedWords ) return sum ( w in s for w in message ) >= 2Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.