刷爆力扣之最常见的单词

简介: 刷爆力扣之最常见的单词

一 🏠 题目描述

819. 最常见的单词


给定一个段落 (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 <= 段落长度 <=10000 <= 禁用单词个数 <=1001 <= 禁用单词长度 <=10

答案是唯一的, 且都是小写字母 (即使在 paragraph 里是大写的,即使是一些特定的名词,答案都是小写的。)

paragraph 只包含字母、空格和下列标点符号!?',;.

不存在没有连字符或者带有连字符的单词。

单词里只包含字母,不会出现省略号或者其他标点符号。


二 🏠破题思路

2.1 🚀 关键信息

解决问题第一步,当然先提取题目字面上的关键信息 😎😎😎


返回出现次数最多 = 【次数最多,直接就是哈希表法】


同时不在禁用列表中的单词 = 【禁用列表单词需忽略】


段落中的单词不区分大小写,答案都是小写字母 = 【段落单词转小写】 🌹🌹🌹



提取完题目中的关键信息后,直接进入第二阶段,思路整理 😃😃😃



2.2 🚀 思路整理

哈希表法


一个哈希集存储禁用单词列表,一个哈希集统计单词计数


遍历段落,当遇到一个字母字符时,将单词长度(wordLen)加加,当遇到一个非字母字符时且词长度(wordLen)不为 0 时,即为一个单词结束 🌻🌻🌻


① 若该单词是禁用单词,则进行往下遍历


② 若该单词不是禁用单词,且未出现在计数哈希集中,则将该单词插入计数哈希集


③ 若该单词不是禁用单词,且已存在于计数哈希集中,则将该单词的计数统计加加


遍历结束处理 wordLen != 0 (即以非禁用单词结尾场景)的特殊情况


最后遍历哈希表,寻找出现次数等于最大计数的单词 🌷🌷🌷



整理完解题思路后,直接进入第三阶段,代码实现 😃😃😃



三 🏠 代码详解

3.1 🚀 代码实现

按照我们刚才的破题思路,直接代码走起来 👇👇👇👇

std::string mostCommonWord(std::string paragraph, std::vector<std::string>& banned) {
    std::unordered_set<char> symbolSet = { '!', '?', '\'', ',', ';', '.', ' ' }; //符号列表
for (auto& elem : paragraph) elem = tolower(elem); //段落单词转小写
  std::unordered_set<std::string> bannedSet(banned.begin(), banned.end()); //禁用单词列表
  std::unordered_map<std::string, int> wordCountMap; //单词计数哈希表
  int wordLen =0, len = paragraph.size(), maxCount =0; //单词长度,文章长度,最大计数
  std::string res =""; //结果字符串
for (int i =0; i < len; ++i) { //遍历数组
if (!symbolSet.count(paragraph[i])) { //当前位置不是标点符号将单词长度加加
++wordLen;
  } elseif (wordLen !=0) { //若为标点符号且 wordLen 不为 0, 单词 = [i - wordLen , i]
    std::string tmpStr(paragraph.begin() + i - wordLen, paragraph.begin() + i);
    wordLen =0; //将单词长度重新置 0if (bannedSet.count(tmpStr)) continue; //若为删除单词, 则直接跳过
if (wordCountMap.count(tmpStr)) ++wordCountMap[tmpStr]; //在计数哈希表,则更新
else wordCountMap[tmpStr] =1; //不在计数哈希表,则插入
  }
  }
if (wordLen !=0) { //处理非禁用单词结尾场景
  std::string tmpStr(paragraph.begin() + len - wordLen, paragraph.begin() + len);
if (wordCountMap.count(tmpStr)) ++wordCountMap[tmpStr]; //在于计数哈希表里
else wordCountMap[tmpStr] =1;
  }
for (auto& elem : wordCountMap) { //遍历单词计数哈希表
if (elem.second > maxCount) maxCount = elem.second , res = elem.first;
  }
  return res; //返回结果
}




3.2 🚀 细节解析

看完 👀👀👀 全注释版的代码实现后,相信看官大大对整体逻辑已经是大写的 OK 了 😃😃😃


那么我们挖掘上述实现的晦涩细节 😖😖😖 进行解析,直接开干,走起来 👇👇👇👇


std::string tmpStr(paragraph.begin() + i - wordLen, paragraph.begin() + i);

若为标点符号且 wordLen 不为 0, 单词 = [i - wordLen , i] 范围的字符序列 🐌🐌🐌



if (elem.second > maxCount) maxCount = elem.second , res = elem.first;

遍历遍历单词计数哈希表,寻找出现次数等于最大计数的单词,将其赋值给 res 🐳🐳🐳


相关文章
|
1月前
Leetcode(最后一个单词长度)
这篇文章介绍了两种解决LeetCode第58题的方法,即计算给定字符串中最后一个单词的长度,方法包括翻转字符串和逆向遍历统计。
18 0
|
1月前
【LeetCode 20】151.反转字符串里的单词
【LeetCode 20】151.反转字符串里的单词
19 0
|
3月前
|
算法
LeetCode第58题最后一个单词的长度
LeetCode第58题"最后一个单词的长度"的解题方法,通过从字符串末尾向前遍历并计数非空格字符,直接得出最后一个单词的长度。
LeetCode第58题最后一个单词的长度
|
3月前
|
算法 JavaScript Python
【Leetcode刷题Python】79. 单词搜索和剑指 Offer 12. 矩阵中的路径
Leetcode第79题"单词搜索"的Python解决方案,使用回溯算法在给定的二维字符网格中搜索单词,判断单词是否存在于网格中。
41 4
|
3月前
|
Python
【Leetcode刷题Python】生词本单词整理
文章提供了一个Python程序,用于帮助用户整理和排版生词本上的单词,包括去除重复单词、按字典序排序,并按照特定的格式要求进行打印排版。
38 3
|
3月前
|
Python
【Leetcode刷题Python】318. 最大单词长度乘积
本文提供了LeetCode题目318的Python编程解决方案,题目要求在一个字符串数组中找出两个不含有公共字母的单词,且这两个单词的长度乘积最大,如果不存在这样的两个单词,则返回0。
17 0
|
5月前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
|
5月前
|
存储 SQL 算法
LeetCode题58: 5种算法实现最后一个单词的长度【python】
LeetCode题58: 5种算法实现最后一个单词的长度【python】
|
5月前
|
算法 测试技术 索引
力扣经典150题第三十二题:串联所有单词的子串
力扣经典150题第三十二题:串联所有单词的子串
26 0
|
5月前
|
算法
力扣经典150题第二十一题:反转字符串中的单词
力扣经典150题第二十一题:反转字符串中的单词
55 0