How do you solve Report Spam Message on LeetCode?

Report Spam Message (LeetCode #3295) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using a HashSet allows for faster lookups compared to an array.

What is the brute force solution for Report Spam Message?

The brute force approach for Report Spam Message is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute-force approach, we check each word in the message against every word in the bannedWords array. This is straightforward but inefficient for large inputs. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Report Spam Message?

Report Spam Message uses the following concepts: Array, Hash Table, String. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Report Spam Message?

Always consider the time complexity of your solution. Explain your thought process clearly and ask clarifying questions. Be prepared to optimize your solution if asked.

What are common mistakes when solving Report Spam Message?

Not using a HashSet for bannedWords, leading to slow lookups. Failing to check if the count reaches 2 before returning.

#3295

Report Spam Message

Medium

ArrayHash TableStringHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

Using a HashSet for bannedWords allows for O(1) average time complexity for lookups. This significantly reduces the time complexity of our solution.

⚙️

Algorithm

5 steps

1Step 1: Convert bannedWords into a HashSet for fast lookups.
2Step 2: Initialize a counter to track matches.
3Step 3: Iterate through each word in the message and check if it exists in the HashSet.
4Step 4: Increment the counter for each match found. If the counter reaches 2, return true.
5Step 5: If the loop completes without finding 2 matches, return false.

solution.py9 lines

1def is_spam(message, bannedWords):
2    bannedSet = set(bannedWords)
3    count = 0
4    for word in message:
5        if word in bannedSet:
6            count += 1
7            if count >= 2:
8                return True
9    return False

ℹ

Complexity note: The time complexity is O(n) because we only pass through the message array once, and lookups in a HashSet are O(1) on average. The space complexity is O(n) due to storing bannedWords in a HashSet.

1Using a HashSet allows for faster lookups compared to an array.
2Counting matches efficiently helps us determine spam quickly.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.