leetcode
leetcode 701 ~ 750
最常见的单词

最常见的单词

难度:

标签:

题目描述

代码结果

运行时间: 27 ms, 内存: 16.0 MB


/*
 思路:
 1. 将段落中的所有字母转换为小写,并用正则表达式去除标点符号。
 2. 将段落分割成单词数组。
 3. 使用一个哈希集合来存储禁用词。
 4. 使用流来统计每个单词的出现频率。
 5. 过滤禁用词并统计非禁用词的频率。
 6. 找出频率最高的非禁用词并返回。
 */

import java.util.*;
import java.util.stream.*;

public class Solution {
    public String mostCommonWord(String paragraph, String[] banned) {
        String normalizedStr = paragraph.replaceAll("[^a-zA-Z ]", " ").toLowerCase();
        List<String> words = Arrays.asList(normalizedStr.split("\s+"));

        Set<String> bannedWords = new HashSet<>(Arrays.asList(banned));

        return words.stream()
                .filter(word -> !bannedWords.contains(word))
                .collect(Collectors.groupingBy(word -> word, Collectors.counting()))
                .entrySet().stream()
                .max(Map.Entry.comparingByValue())
                .get()
                .getKey();
    }
}

解释

方法:

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

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
在题解中,为什么选择使用正则表达式来处理段落中的非字母、数字、空格字符,而不是其他方法?
使用正则表达式来处理非字母、数字、空格字符是因为正则表达式提供了一种灵活、高效的方式来匹配和替换文本中满足特定模式的字符串。这种方法可以一次性替换所有不符合条件的字符,大大简化了代码的复杂性,并且提高了处理速度。相比之下,其他方法如逐字符判断和替换可能会更加繁琐且执行效率较低。
🦆
题解假设了禁用词列表中的单词都是小写,如果禁用词列表中存在大写怎么处理?
如果禁用词列表中存在大写单词,为了确保所有的禁用词都能被正确识别和过滤,应该在处理之前将禁用词列表中的所有单词转换为小写。这样做可以保证无论输入单词的大小写如何,都能与处理后统一为小写的段落文本匹配,确保算法的准确性和一致性。
🦆
题解中提到,如果存在禁用词则仅将禁用词列表的第一个元素转为小写,这种处理方式是否适用于所有可能的输入情况?
这种处理方式并不适用于所有可能的输入情况。只将禁用词列表的第一个元素转为小写可能导致其他未转化的禁用词无法被正确识别和过滤。正确的做法应该是将禁用词列表中的所有单词都转换为小写,以确保所有禁用词无论原始格式如何,都能被算法正确处理。
🦆
在统计单词频率时,题解使用了默认字典(defaultdict),请问这种数据结构的选择与普通字典有何优势?
使用默认字典(defaultdict)主要的优势在于它可以自动为尚未存在于字典中的键提供一个默认值。这在统计词频时特别有用,因为它免去了每次在增加计数之前检查键是否存在的需求。这样不仅可以简化代码,还能提高执行效率。与普通字典相比,使用默认字典在处理不存在的键时更加方便和高效。

相关问题