TNotes.leetcode

Appearance

0819. 最常见的单词【简单】

0819. 最常见的单词【简单】 ​

1. 📝 题目描述 ​

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

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

注意 单词不包含标点符号。

示例 1：

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

示例 2：

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

提示：

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

2. 🫧 评价 ​

  • 解法 1 逻辑更清晰，分步骤处理
  • 解法 2 更紧凑，实时更新结果
  • 从渐进复杂度分析来看，两者是相同的，但解法 2 在实际应用中可能具有轻微的性能优势。

3. 🎯 s.1 - 两次遍历 ​

js
/**
 * @param {string} paragraph
 * @param {string[]} banned
 * @return {string}
 */
var mostCommonWord = function (paragraph, banned) {
  // 将禁用单词列表转换为 Set
  const bannedSet = new Set(banned)

  // 使用正则表达式提取所有单词并转换为小写
  const words = paragraph.toLowerCase().match(/[a-z]+/g) || []

  // 使用哈希表统计每个非禁用单词的出现次数
  const wordCount = new Map()
  for (const word of words) {
    if (!bannedSet.has(word)) {
      wordCount.set(word, (wordCount.get(word) || 0) + 1)
    }
  }

  // 找出出现次数最多的单词
  let maxCount = 0
  let result = ''

  for (const [word, count] of wordCount) {
    if (count > maxCount) {
      maxCount = count
      result = word
    }
  }

  return result
}
  • 算法复杂度
    • 时间复杂度：O(n+m+k)
    • 空间复杂度：O(m+k)
    • 其中 n 是段落长度，m 是禁用单词数量，k 是提取出的单词数量。时间复杂度主要由三部分组成：遍历段落构建禁用词集合 O(m)、正则提取单词 O(n)、遍历单词统计词频 O(k)。空间复杂度主要由禁用词集合 O(m) 和词频统计 Map O(k) 决定。
  • 核心思路
    • 分两步进行，先统计完再查找最大值。

4. 🎯 s.2 - 一次遍历 ​

js
/**
 * @param {string} paragraph
 * @param {string[]} banned
 * @return {string}
 */
var mostCommonWord = function (paragraph, banned) {
  // 将禁用词转为 Set，提高查找效率
  const bannedSet = new Set(banned)

  // 使用正则提取所有单词（只包含字母），并转为小写
  const words = paragraph.toLowerCase().match(/[a-z]+/g)

  // 用于统计词频
  const freq = {}
  let maxCount = 0
  let result = ''

  for (const word of words) {
    // 跳过禁用词
    if (bannedSet.has(word)) continue

    // 统计频率
    freq[word] = (freq[word] || 0) + 1

    // 实时更新最高频词
    if (freq[word] > maxCount) {
      maxCount = freq[word]
      result = word
    }
  }

  return result
}
  • 算法复杂度（同 Solutions.1）
    • 时间复杂度：O(n+m+k)
    • 空间复杂度：O(m+k)
  • 核心思路
    • 边统计边查找最大值

Discussions