最常见的单词

标签: 数组 哈希表 字符串 计数

难度: Easy

给你一个字符串 paragraph 和一个表示禁用词的字符串数组 banned ，返回出现频率最高的非禁用词。题目数据 保证 至少存在一个非禁用词，且答案 唯一 。

paragraph 中的单词 不区分大小写 ，答案应以 小写 形式返回。

示例 1：

输入：paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.", banned = ["hit"]
输出："ball"
解释：
"hit" 出现了 3 次，但它是禁用词。
"ball" 出现了两次（没有其他单词出现这么多次），因此它是段落中出现频率最高的非禁用词。
请注意，段落中的单词不区分大小写，
标点符号会被忽略（即使它们紧挨着单词，如 "ball,"），
并且尽管 "hit" 出现的次数更多，但它不能作为答案，因为它是禁用词。

示例 2：

输入：paragraph = "a.", banned = []
输出："a"

提示：

  • 1 <= paragraph.length <= 1000
  • paragraph 由英文字母、空格 ' '、和以下符号组成："!?',;."
  • 0 <= banned.length <= 100
  • 1 <= banned[i].length <= 10
  • banned[i] 仅由小写英文字母组成

Submission

运行时间: 27 ms

内存: 16.0 MB

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        paragraph = paragraph.lower()
        paragraph = re.sub(r'[^\w\s]', ' ', paragraph)
        paragraph1 = paragraph.split()
        n = len(paragraph1)
        dic = defaultdict()
        if len(banned):
            banned[0] = banned[0].lower()
        for i in range(n):
            if paragraph1[i] not in banned:
                if paragraph1[i] in dic.keys():
                    dic[paragraph1[i]] += 1
                else:
                    dic[paragraph1[i]] = 1
        ans = ''
        res = 0
        for item in dic.items():
            if item[1] > res:
                res = item[1]
                ans = item[0]
        return ans

Explain

该题解的思路是：首先将整个段落转为小写，并使用正则表达式将所有非字母、数字、空格的字符替换为空格。然后将处理后的段落按空格分割成单词列表。如果存在禁用词，则将禁用词列表的第一个元素转为小写（假设禁用词列表中的单词都是小写）。接下来遍历单词列表，对于不在禁用词列表中的单词，统计其出现的频率，并使用哈希表存储每个单词及其对应的频率。最后遍历哈希表，找出频率最高的单词作为答案返回。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        # 将段落转为小写
        paragraph = paragraph.lower()
        # 使用正则表达式将非字母、数字、空格的字符替换为空格
        paragraph = re.sub(r'[^\w\s]', ' ', paragraph)
        # 将处理后的段落按空格分割成单词列表
        paragraph1 = paragraph.split()
        n = len(paragraph1)
        # 使用默认字典存储单词及其频率
        dic = defaultdict()
        # 如果存在禁用词，将禁用词列表的第一个元素转为小写
        if len(banned):
            banned[0] = banned[0].lower()
        # 遍历单词列表，统计不在禁用词列表中的单词的频率
        for i in range(n):
            if paragraph1[i] not in banned:
                if paragraph1[i] in dic.keys():
                    dic[paragraph1[i]] += 1
                else:
                    dic[paragraph1[i]] = 1
        ans = ''
        res = 0
        # 遍历哈希表，找出频率最高的单词作为答案
        for item in dic.items():
            if item[1] > res:
                res = item[1]
                ans = item[0]
        return ans

Explore

使用正则表达式来处理非字母、数字、空格字符是因为正则表达式提供了一种灵活、高效的方式来匹配和替换文本中满足特定模式的字符串。这种方法可以一次性替换所有不符合条件的字符，大大简化了代码的复杂性，并且提高了处理速度。相比之下，其他方法如逐字符判断和替换可能会更加繁琐且执行效率较低。

如果禁用词列表中存在大写单词，为了确保所有的禁用词都能被正确识别和过滤，应该在处理之前将禁用词列表中的所有单词转换为小写。这样做可以保证无论输入单词的大小写如何，都能与处理后统一为小写的段落文本匹配，确保算法的准确性和一致性。

这种处理方式并不适用于所有可能的输入情况。只将禁用词列表的第一个元素转为小写可能导致其他未转化的禁用词无法被正确识别和过滤。正确的做法应该是将禁用词列表中的所有单词都转换为小写，以确保所有禁用词无论原始格式如何，都能被算法正确处理。

使用默认字典（defaultdict）主要的优势在于它可以自动为尚未存在于字典中的键提供一个默认值。这在统计词频时特别有用，因为它免去了每次在增加计数之前检查键是否存在的需求。这样不仅可以简化代码，还能提高执行效率。与普通字典相比，使用默认字典在处理不存在的键时更加方便和高效。