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" 出现了2次（没有其他单词出现得更频繁），所以它是出现频率最高的非禁用词。
注意，段落中的单词不区分大小写，
标点符号被忽略（即使与单词相邻，如"ball,"），
"hit"不是答案，尽管它出现次数更多，因为它是禁用词。

示例 2：

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

提示：

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

解题思路

解题思路

这道题的核心是统计单词频次并找出最频繁的非禁用词。可以分为以下几个步骤：

步骤分析：

  1. 文本处理：将段落中的标点符号替换为空格，然后按空格分割成单词数组
  2. 标准化：将所有单词转换为小写，确保大小写不敏感的比较
  3. 构建禁用词集合：将禁用词数组转换为哈希集合，提高查找效率
  4. 统计频次：遍历单词数组，对于非禁用词进行计数
  5. 找出最大值：在统计过程中记录出现频次最高的单词

算法优化点：

  • 使用哈希表存储禁用词，查找时间复杂度为O(1)
  • 使用哈希表统计词频，避免重复遍历
  • 在统计过程中同时记录最大频次和对应单词，避免额外遍历

这种方法简洁高效，一次遍历即可完成所有操作。

代码实现

class Solution {
public:
    string mostCommonWord(string paragraph, vector<string>& banned) {
        // 替换标点符号为空格
        for (char& c : paragraph) {
            if (!isalpha(c)) c = ' ';
            else c = tolower(c);
        }
        
        // 构建禁用词集合
        unordered_set<string> bannedSet(banned.begin(), banned.end());
        
        // 分割单词并统计频次
        unordered_map<string, int> wordCount;
        stringstream ss(paragraph);
        string word;
        string result;
        int maxCount = 0;
        
        while (ss >> word) {
            if (bannedSet.find(word) == bannedSet.end()) {
                wordCount[word]++;
                if (wordCount[word] > maxCount) {
                    maxCount = wordCount[word];
                    result = word;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        import re
        
        # 转换为小写并用正则表达式分割单词
        words = re.findall(r'\w+', paragraph.lower())
        
        # 构建禁用词集合
        banned_set = set(banned)
        
        # 统计词频
        word_count = {}
        max_count = 0
        result = ""
        
        for word in words:
            if word not in banned_set:
                word_count[word] = word_count.get(word, 0) + 1
                if word_count[word] > max_count:
                    max_count = word_count[word]
                    result = word
        
        return result

public class Solution {
    public string MostCommonWord(string paragraph, string[] banned) {
        // 转换为小写并替换标点符号
        paragraph = paragraph.ToLower();
        foreach (char c in "!?',;.")
        {
            paragraph = paragraph.Replace(c, ' ');
        }
        
        // 构建禁用词集合
        var bannedSet = new HashSet<string>(banned);
        
        // 分割单词并统计频次
        string[] words = paragraph.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
        var wordCount = new Dictionary<string, int>();
        string result = "";
        int maxCount = 0;
        
        foreach (string word in words)
        {
            if (!bannedSet.Contains(word))
            {
                wordCount[word] = wordCount.GetValueOrDefault(word, 0) + 1;
                if (wordCount[word] > maxCount)
                {
                    maxCount = wordCount[word];
                    result = word;
                }
            }
        }
        
        return result;
    }
}

var mostCommonWord = function(paragraph, banned) {
    // 转换为小写并用正则表达式分割单词
    const words = paragraph.toLowerCase().match(/\w+/g) || [];
    
    // 构建禁用词集合
    const bannedSet = new Set(banned);
    
    // 统计词频
    const wordCount = new Map();
    let maxCount = 0;
    let result = "";
    
    for (const word of words) {
        if (!bannedSet.has(word)) {
            const count = (wordCount.get(word) || 0) + 1;
            wordCount.set(word, count);
            if (count > maxCount) {
                maxCount = count;
                result = word;
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n + m)n 为段落长度，m 为禁用词数量。需要遍历段落一次进行分词和统计
空间复杂度O(k + m)k 为不同单词的数量，m 为禁用词数量。需要存储词频表和禁用词集合