原文链接: https://leetcode-cn.com/problems/most-common-word

英文原文

Given a string paragraph and a string array of the banned words banned, return the most frequent word that is not banned. It is guaranteed there is at least one word that is not banned, and that the answer is unique.

The words in paragraph are case-insensitive and the answer should be returned in lowercase.

 

Example 1:

Input: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.", banned = ["hit"]
Output: "ball"
Explanation: 
"hit" occurs 3 times, but it is a banned word.
"ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. 
Note that words in the paragraph are not case sensitive,
that punctuation is ignored (even if adjacent to words, such as "ball,"), 
and that "hit" isn't the answer even though it occurs more because it is banned.

Example 2:

Input: paragraph = "a.", banned = []
Output: "a"

 

Constraints:

• 1 <= paragraph.length <= 1000
• paragraph consists of English letters, space ' ', or one of the symbols: "!?',;.".
• 0 <= banned.length <= 100
• 1 <= banned[i].length <= 10
• banned[i] consists of only lowercase English letters.

中文题目

给定一个段落 (paragraph) 和一个禁用单词列表 (banned)。返回出现次数最多，同时不在禁用列表中的单词。

题目保证至少有一个词不在禁用列表中，而且答案唯一。

禁用列表中的单词用小写字母表示，不含标点符号。段落中的单词不区分大小写。答案都是小写字母。

 

示例：

输入: 
paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."
banned = ["hit"]
输出: "ball"
解释: 
"hit" 出现了3次，但它是一个禁用的单词。
"ball" 出现了2次 (同时没有其他单词出现2次)，所以它是段落里出现次数最多的，且不在禁用列表中的单词。 
注意，所有这些单词在段落里不区分大小写，标点符号需要忽略（即使是紧挨着单词也忽略， 比如 "ball,"）， 
"hit"不是最终的答案，虽然它出现次数更多，但它在禁用单词列表中。

 

提示：

• 1 <= 段落长度 <= 1000
• 0 <= 禁用单词个数 <= 100
• 1 <= 禁用单词长度 <= 10
• 答案是唯一的, 且都是小写字母 (即使在 paragraph 里是大写的，即使是一些特定的名词，答案都是小写的。)
• paragraph 只包含字母、空格和下列标点符号!?',;.
• 不存在没有连字符或者带有连字符的单词。
• 单词里只包含字母，不会出现省略号或者其他标点符号。

通过代码

官方题解

简单计数：

我们统计出每个单词出现的次数，忽略所有的标点符号和大小写，答案即为出现次数最多且不在禁用列表中的那个单词。

统计单词的方法有两种。在第一种方法中，我们首先对整个段落按照空格进行分词（split），然后对于分出的每个单词，我们移除标点符号并忽略大小写。在第二种方法中，我们逐字符扫描整个段落，如果遇到一个非字母的符号，那就把之前遇到的字母作为一个单词。

对于每一个单词，我们会放入哈希映射（Java 中的 HashMap 或者 Python 中的 Counter）中进行计数。在每次放入单词之后，如果这个单词不在禁用列表中，我们就可以更新一次答案。

[sol1]
class Solution {
    public String mostCommonWord(String paragraph, String[] banned) {
        paragraph += ".";

        Set<String> banset = new HashSet();
        for (String word: banned) banset.add(word);
        Map<String, Integer> count = new HashMap();

        String ans = "";
        int ansfreq = 0;

        StringBuilder word = new StringBuilder();
        for (char c: paragraph.toCharArray()) {
            if (Character.isLetter(c)) {
                word.append(Character.toLowerCase(c));
            } else if (word.length() > 0) {
                String finalword = word.toString();
                if (!banset.contains(finalword)) {
                    count.put(finalword, count.getOrDefault(finalword, 0) + 1);
                    if (count.get(finalword) > ansfreq) {
                        ans = finalword;
                        ansfreq = count.get(finalword);
                    }
                }
                word = new StringBuilder();
            }
        }

        return ans;
    }
}

[sol1]
class Solution(object):
    def mostCommonWord(self, paragraph, banned):
        banset = set(banned)
        for c in "!?',;.":
            paragraph = paragraph.replace(c, " ")
        count = collections.Counter(
            word for word in paragraph.lower().split())

        ans, best = '', 0
        for word in count:
            if count[word] > best and word not in banset:
                ans, best = word, count[word]

        return ans

复杂度分析

• 时间复杂度：$O(P + B)$，其中 $P$ 是段落 paragraph 的长度，$B$ 是禁用列表 banned 的长度。

• 空间复杂度：$O(P + B)$，用来进行计数以及存储禁用列表 banned。

统计信息

通过次数	提交次数	AC比率
23074	54731	42.2%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言