一 🏠 题目描述
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 🐳🐳🐳