What is the optimal solution for the 'Report Spam Message' problem?

The optimal solution uses array scanning with a hash set for fast lookups, ensuring the solution runs in O(n + m) time.

Why should I use a hash set in this problem?

A hash set allows for constant time lookups, which is crucial for handling large input sizes efficiently in this problem.

What happens if I don't optimize for early exit?

Failing to optimize for early exit will result in unnecessary checks, slowing down the algorithm when spam conditions are met early in the message array.

How do I handle empty arrays in the 'Report Spam Message' problem?

You should return false if either the `message` or `bannedWords` array is empty, as there can't be any matches.

What are the edge cases to consider for this problem?

Edge cases include empty arrays, arrays where no banned words are present, and arrays where all words are banned.

#3295

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

举报垃圾信息

给你一个字符串数组 message 和一个字符串数组 bannedWords 。如果数组中至少存在两个单词与 bannedWords 中的任一单词完全相同，则该数组被视为垃圾信息。如果数组 message 是垃圾信息，则返回 true ；否则返回 false 。示例 1：输入： …

数组哈希表字符串

题目描述

给你一个字符串数组 message 和一个字符串数组 bannedWords。

如果数组中至少存在两个单词与 bannedWords 中的任一单词 完全相同，则该数组被视为 垃圾信息。

如果数组 message 是垃圾信息，则返回 true；否则返回 false。

示例 1：

输入： message = ["hello","world","leetcode"], bannedWords = ["world","hello"]

输出： true

解释：

数组 message 中的 "hello" 和 "world" 都出现在数组 bannedWords 中。

示例 2：

输入： message = ["hello","programming","fun"], bannedWords = ["world","programming","leetcode"]

输出： false

解释：

数组 message 中只有一个单词（"programming"）出现在数组 bannedWords 中。

提示：

1 <= message.length, bannedWords.length <= 10⁵
1 <= message[i].length, bannedWords[i].length <= 15
message[i] 和 bannedWords[i] 都只由小写英文字母组成。

lightbulb

解题思路

方法一：哈希表

我们用一个哈希表 $s$ 存储 $\textit{bannedWords}$ 中的所有单词，然后遍历 $\textit{message}$ 中的每个单词，如果单词在哈希表 $s$ 中出现，我们就将计数器 $cnt$ 加一，如果 $cnt$ 大于等于 $2$ ，我们就返回 $\text{true}$ ，否则返回 $\text{false}$ 。

时间复杂度 $O((n + m) \times |w|)$ ，空间复杂度 $O(m \times |w|)$ 。其中 $n$ 是数组 $\textit{message}$ 的长度，而 $m$ 和 $|w|$ 分别是数组 $\textit{bannedWords}$ 的长度和数组中单词的最大长度。

1

2

3

4

5

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for the candidate's ability to implement efficient searching using a hash set.
question_mark
Evaluate the candidate's approach to optimizing for early exits.
question_mark
Test the candidate's understanding of time complexity, particularly with large arrays.

warning

常见陷阱

外企场景

error
Incorrect handling of case sensitivity: The problem specifies lowercase letters only, but candidates might mistakenly use case-insensitive checks.
error
Not using a hash set: A naive approach without hash sets could lead to slow performance for large inputs.
error
Failing to optimize for early exit: Checking the entire array even after finding two banned words is inefficient.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Instead of returning true or false, return the list of banned words found in the message.
arrow_right_alt
Handle edge cases where the `message` or `bannedWords` arrays are empty.
arrow_right_alt
Optimize for constant space complexity by scanning the array and checking banned words inline without using a hash set.

help

常见问题

外企场景

继续练习

#3316 从原字符串里进行删除操作的最多次数 #3327 判断 DFS 字符串是否是回文串 #3331 修改后子树的大小