LeetCode-Go 题解 819Most Common Word——哈希计数求解最高频非禁用单词【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文以开源仓库 LeetCode-Go 中 0819.Most-Common-Word 题解 为主线完整讲解 LeetCode 819 Most Common Word最常见的单词的题意、约束、解题思路与 Go 源码实现。这是一道典型的字符串分词 哈希表频次统计简单题读完本文你将掌握如何对含标点的段落做单词切分、如何统一大小写、如何剔除禁用词以及如何在 O(n) 时间内返回唯一最高频的合法单词并可从仓库中对应的源码与测试用例直接验证。题目描述给定一个段落paragraph和一个禁用单词列表banned返回段落中出现次数最多、且不在禁用列表中的单词。题目保证至少存在一个不在禁用列表中的单词且答案唯一。需要注意的规则禁用列表中的单词全部为小写且不含标点段落中的单词不区分大小写大小写敏感度不敏感最终答案必须是小写字母即使它在段落中以大写或专有名词形式出现段落仅由字母、空格以及标点符号!?,;.组成段落中不存在连字符hyphen或带连字符的单词单词只由字母组成绝不包含撇号或其他标点符号。示例Input: paragraph Bob hit a ball, the hit BALL flew far after it was hit. banned [hit] Output: ball解释hit出现了 3 次但它是禁用词不能作为答案ball出现了 2 次没有其他单词出现更多所以它是段落中出现次数最多的非禁用单词段落中的单词不区分大小写ball与BALL视为同一个词标点会被忽略即使紧贴在单词旁例如ball,中的逗号尽管hit出现次数更多但因为被禁用所以不是答案。题目大意中文给定一个段落paragraph和一个禁用单词列表banned返回出现次数最多、同时不在禁用列表中的单词。题目保证至少有一个词不在禁用列表中而且答案唯一。禁用列表中的单词用小写字母表示不含标点符号。段落中的单词不区分大小写答案一律为小写字母。题目约束与边界分析原题约束如下理解这些约束对设计算法边界非常关键1 paragraph.length 1000段落非空长度不超过 10000 banned.length 100禁用列表可能为空为空时退化为求全段落最高频单词1 banned[i].length 10每个禁用词长度不超过 10答案是唯一的并且以小写形式给出段落只包含字母、空格和标点!?,;.。从约束可以得出两个重要的边界推论禁用列表可能为空此时只需统计段落中全部单词的频次并取最大值段落首尾都可能是单词而非标点最后一个单词后面不一定跟分隔符因此在遍历结束后需要单独处理未收尾的最后一个单词——仓库源码中的if start ! -1分支正是为此而设计。解题思路哈希表统计 剔除禁用词整体思路非常直接共三步分词并统计频次按空格和标点!?,;.作为分隔符将段落切成一个个单词对每个单词做ToLower统一为小写存入map[string]int累加频次剔除禁用词遍历banned列表用delete(freqMap, bannedWord)从频次表中删除所有禁用词取最大值遍历频次表找出频次最高的单词返回。由于题目保证答案唯一出现次数相同时无需处理并列的情况。这种先统计、后过滤、再取极值的三段式流程正是哈希表在词频统计类问题上的经典用法。完整思路可参见 题解文档 中的解题思路一节。源码实现解析仓库中的核心实现位于 819. Most Common Word.go函数签名与完整逻辑如下package leetcode import strings func mostCommonWord(paragraph string, banned []string) string { freqMap, start : make(map[string]int), -1 for i, c : range paragraph { if c || c ! || c ? || c \ || c , || c ; || c . { if start -1 { word : strings.ToLower(paragraph[start:i]) freqMap[word] } start -1 } else { if start -1 { start i } } } if start ! -1 { word : strings.ToLower(paragraph[start:]) freqMap[word] } // Strip the banned words from the freqmap for _, bannedWord : range banned { delete(freqMap, bannedWord) } // Find most freq word mostFreqWord, mostFreqCount : , 0 for word, freq : range freqMap { if freq mostFreqCount { mostFreqWord word mostFreqCount freq } } return mostFreqWord }下面逐段拆解实现细节。第一段手工分词不使用 strings.Fields 的原因freqMap, start : make(map[string]int), -1 for i, c : range paragraph { if c || c ! || c ? || c \ || c , || c ; || c . { // 命中分隔符若 start 0 说明正在积累一个单词切出该单词 ... start -1 } else { // 普通字符记录单词起始位置 if start -1 { start i } } }这里的关键设计是使用start指针标记当前单词的起始下标而不是直接使用strings.Fields或strings.Split。原因在于段落中的分隔符除了空格还包括!?,;.六种标点且标点可能与单词紧邻如ball,标点之间可能连续出现如a,,b需要把连续分隔符合并处理用start -1表示当前不在单词内只有在从分隔符切换到字母时才记录起点天然规避了连续分隔符和段落开头就是标点的情况。for i, c : range paragraph中i是字节下标c是 rune。由于题目保证段落只含字母、空格与限定标点均为 ASCII 字符这里用字节下标切片paragraph[start:i]是安全的strings.ToLower用于统一大小写使ball与BALL归并为同一个键。第二段收尾处理最后一个单词if start ! -1 { word : strings.ToLower(paragraph[start:]) freqMap[word] }当段落以单词结尾没有尾随标点时循环结束后start仍指向最后一个单词的起点此时需要把paragraph[start:]整体作为一个单词入表。这一分支不可省略例如用例a a a b b的最后一个b就依赖它被统计进去。第三段剔除禁用词for _, bannedWord : range banned { delete(freqMap, bannedWord) }直接对 map 执行delete把禁用词从频次表中移除。这样做相比统计时跳过禁用词的好处是代码职责单一、可读性高且banned长度最大只有 100删除开销可忽略。即便禁用词在段落中根本没出现delete对不存在的键也不会产生任何副作用。第四段遍历取最高频mostFreqWord, mostFreqCount : , 0 for word, freq : range freqMap { if freq mostFreqCount { mostFreqWord word mostFreqCount freq } } return mostFreqWord采用大于才更新的比较策略。由于题目保证答案唯一无需处理频次并列的情况mostFreqWord初始为空串在答案唯一且至少有一个非禁用词的保证下最终必然被真实单词覆盖。复杂度分析时间复杂度O(n m)其中 n 为paragraph长度m 为banned长度。分词与统计各字符遍历一遍为 O(n)剔除禁用词与查找最大值各遍历一遍为 O(m) 与 O(k)k 为去重后的单词数k ≤ n总体线性空间复杂度O(k)freqMap最多容纳段落中去重后的单词数最坏情况下 O(n)。该算法一次线性遍历即可完成分词与统计空间占用仅与不同单词数相关在paragraph.length 1000的约束下开销非常小。测试用例验证仓库中提供了对应的表驱动测试 819. Most Common Word_test.go覆盖了两个代表性场景输入段落banned期望输出Bob hit a ball, the hit BALL flew far after it was hit.[hit]balla a a b b[]a第一个用例即题目官方示例同时验证了三点大小写不敏感BALL与ball同词、标点剔除ball,中的逗号、禁用词排除出现 3 次的hit被丢弃第二个用例验证了banned为空时的退化行为——此时直接返回全段落最高频单词a。测试文件沿用了仓库统一的表驱动测试风格question819结构体聚合para819参数与ans819期望答案在Test_Problem819中循环执行mostCommonWord(p.one, p.b)并打印输入输出。若在本地具备 Go 环境可在仓库根目录执行go test ./leetcode/0819.Most-Common-Word/运行该测试当前环境未安装 Go测试需在有 Go toolchain 的机器上执行。边界情况与扩展思考结合源码实现以下边界场景值得注意段落以标点结尾如ball,分词在循环内完成start会被重置为 -1收尾分支不会误加空串段落以单词结尾依赖第二段的收尾分支这是最容易遗漏的 corner casebanned为空delete循环不执行直接返回全段落最高频词段落首字符就是标点或空格start保持 -1不会产生空单词入表连续多个分隔符start在遇到第一个分隔符后即为 -1后续分隔符不会重复触发切片。扩展思考若题目改为大小写敏感或需要返回前 K 高频词本实现只需去掉strings.ToLower或改为维护topK容器如最小堆若段落中出现连字符单词则需把-也加入分隔符集合。这些变体均可在本实现基础上最小化改动。小结LeetCode 819 Most Common Word 是一道字符串处理 哈希表的入门题核心考点是正确的单词切分处理标点与大小写与统计—过滤—取极值的流程组织。仓库 LeetCode-Go 通过start指针手工分词的方式在单次线性遍历内同时完成了切词与计数实现简洁、无额外依赖并配有覆盖官方示例与空禁用列表两种场景的单元测试可作为该类型题目的标准参考答案。如需查看完整源码与文档可继续阅读 题解 README、核心实现 与 单元测试。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Go 题解 819：Most Common Word——哈希计数求解最高频非禁用单词
LeetCode-Go 题解 819Most Common Word——哈希计数求解最高频非禁用单词【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文以开源仓库 LeetCode-Go 中 0819.Most-Common-Word 题解 为主线完整讲解 LeetCode 819 Most Common Word最常见的单词的题意、约束、解题思路与 Go 源码实现。这是一道典型的字符串分词 哈希表频次统计简单题读完本文你将掌握如何对含标点的段落做单词切分、如何统一大小写、如何剔除禁用词以及如何在 O(n) 时间内返回唯一最高频的合法单词并可从仓库中对应的源码与测试用例直接验证。题目描述给定一个段落paragraph和一个禁用单词列表banned返回段落中出现次数最多、且不在禁用列表中的单词。题目保证至少存在一个不在禁用列表中的单词且答案唯一。需要注意的规则禁用列表中的单词全部为小写且不含标点段落中的单词不区分大小写大小写敏感度不敏感最终答案必须是小写字母即使它在段落中以大写或专有名词形式出现段落仅由字母、空格以及标点符号!?,;.组成段落中不存在连字符hyphen或带连字符的单词单词只由字母组成绝不包含撇号或其他标点符号。示例Input: paragraph Bob hit a ball, the hit BALL flew far after it was hit. banned [hit] Output: ball解释hit出现了 3 次但它是禁用词不能作为答案ball出现了 2 次没有其他单词出现更多所以它是段落中出现次数最多的非禁用单词段落中的单词不区分大小写ball与BALL视为同一个词标点会被忽略即使紧贴在单词旁例如ball,中的逗号尽管hit出现次数更多但因为被禁用所以不是答案。题目大意中文给定一个段落paragraph和一个禁用单词列表banned返回出现次数最多、同时不在禁用列表中的单词。题目保证至少有一个词不在禁用列表中而且答案唯一。禁用列表中的单词用小写字母表示不含标点符号。段落中的单词不区分大小写答案一律为小写字母。题目约束与边界分析原题约束如下理解这些约束对设计算法边界非常关键1 paragraph.length 1000段落非空长度不超过 10000 banned.length 100禁用列表可能为空为空时退化为求全段落最高频单词1 banned[i].length 10每个禁用词长度不超过 10答案是唯一的并且以小写形式给出段落只包含字母、空格和标点!?,;.。从约束可以得出两个重要的边界推论禁用列表可能为空此时只需统计段落中全部单词的频次并取最大值段落首尾都可能是单词而非标点最后一个单词后面不一定跟分隔符因此在遍历结束后需要单独处理未收尾的最后一个单词——仓库源码中的if start ! -1分支正是为此而设计。解题思路哈希表统计 剔除禁用词整体思路非常直接共三步分词并统计频次按空格和标点!?,;.作为分隔符将段落切成一个个单词对每个单词做ToLower统一为小写存入map[string]int累加频次剔除禁用词遍历banned列表用delete(freqMap, bannedWord)从频次表中删除所有禁用词取最大值遍历频次表找出频次最高的单词返回。由于题目保证答案唯一出现次数相同时无需处理并列的情况。这种先统计、后过滤、再取极值的三段式流程正是哈希表在词频统计类问题上的经典用法。完整思路可参见 题解文档 中的解题思路一节。源码实现解析仓库中的核心实现位于 819. Most Common Word.go函数签名与完整逻辑如下package leetcode import strings func mostCommonWord(paragraph string, banned []string) string { freqMap, start : make(map[string]int), -1 for i, c : range paragraph { if c || c ! || c ? || c \ || c , || c ; || c . { if start -1 { word : strings.ToLower(paragraph[start:i]) freqMap[word] } start -1 } else { if start -1 { start i } } } if start ! -1 { word : strings.ToLower(paragraph[start:]) freqMap[word] } // Strip the banned words from the freqmap for _, bannedWord : range banned { delete(freqMap, bannedWord) } // Find most freq word mostFreqWord, mostFreqCount : , 0 for word, freq : range freqMap { if freq mostFreqCount { mostFreqWord word mostFreqCount freq } } return mostFreqWord }下面逐段拆解实现细节。第一段手工分词不使用 strings.Fields 的原因freqMap, start : make(map[string]int), -1 for i, c : range paragraph { if c || c ! || c ? || c \ || c , || c ; || c . { // 命中分隔符若 start 0 说明正在积累一个单词切出该单词 ... start -1 } else { // 普通字符记录单词起始位置 if start -1 { start i } } }这里的关键设计是使用start指针标记当前单词的起始下标而不是直接使用strings.Fields或strings.Split。原因在于段落中的分隔符除了空格还包括!?,;.六种标点且标点可能与单词紧邻如ball,标点之间可能连续出现如a,,b需要把连续分隔符合并处理用start -1表示当前不在单词内只有在从分隔符切换到字母时才记录起点天然规避了连续分隔符和段落开头就是标点的情况。for i, c : range paragraph中i是字节下标c是 rune。由于题目保证段落只含字母、空格与限定标点均为 ASCII 字符这里用字节下标切片paragraph[start:i]是安全的strings.ToLower用于统一大小写使ball与BALL归并为同一个键。第二段收尾处理最后一个单词if start ! -1 { word : strings.ToLower(paragraph[start:]) freqMap[word] }当段落以单词结尾没有尾随标点时循环结束后start仍指向最后一个单词的起点此时需要把paragraph[start:]整体作为一个单词入表。这一分支不可省略例如用例a a a b b的最后一个b就依赖它被统计进去。第三段剔除禁用词for _, bannedWord : range banned { delete(freqMap, bannedWord) }直接对 map 执行delete把禁用词从频次表中移除。这样做相比统计时跳过禁用词的好处是代码职责单一、可读性高且banned长度最大只有 100删除开销可忽略。即便禁用词在段落中根本没出现delete对不存在的键也不会产生任何副作用。第四段遍历取最高频mostFreqWord, mostFreqCount : , 0 for word, freq : range freqMap { if freq mostFreqCount { mostFreqWord word mostFreqCount freq } } return mostFreqWord采用大于才更新的比较策略。由于题目保证答案唯一无需处理频次并列的情况mostFreqWord初始为空串在答案唯一且至少有一个非禁用词的保证下最终必然被真实单词覆盖。复杂度分析时间复杂度O(n m)其中 n 为paragraph长度m 为banned长度。分词与统计各字符遍历一遍为 O(n)剔除禁用词与查找最大值各遍历一遍为 O(m) 与 O(k)k 为去重后的单词数k ≤ n总体线性空间复杂度O(k)freqMap最多容纳段落中去重后的单词数最坏情况下 O(n)。该算法一次线性遍历即可完成分词与统计空间占用仅与不同单词数相关在paragraph.length 1000的约束下开销非常小。测试用例验证仓库中提供了对应的表驱动测试 819. Most Common Word_test.go覆盖了两个代表性场景输入段落banned期望输出Bob hit a ball, the hit BALL flew far after it was hit.[hit]balla a a b b[]a第一个用例即题目官方示例同时验证了三点大小写不敏感BALL与ball同词、标点剔除ball,中的逗号、禁用词排除出现 3 次的hit被丢弃第二个用例验证了banned为空时的退化行为——此时直接返回全段落最高频单词a。测试文件沿用了仓库统一的表驱动测试风格question819结构体聚合para819参数与ans819期望答案在Test_Problem819中循环执行mostCommonWord(p.one, p.b)并打印输入输出。若在本地具备 Go 环境可在仓库根目录执行go test ./leetcode/0819.Most-Common-Word/运行该测试当前环境未安装 Go测试需在有 Go toolchain 的机器上执行。边界情况与扩展思考结合源码实现以下边界场景值得注意段落以标点结尾如ball,分词在循环内完成start会被重置为 -1收尾分支不会误加空串段落以单词结尾依赖第二段的收尾分支这是最容易遗漏的 corner casebanned为空delete循环不执行直接返回全段落最高频词段落首字符就是标点或空格start保持 -1不会产生空单词入表连续多个分隔符start在遇到第一个分隔符后即为 -1后续分隔符不会重复触发切片。扩展思考若题目改为大小写敏感或需要返回前 K 高频词本实现只需去掉strings.ToLower或改为维护topK容器如最小堆若段落中出现连字符单词则需把-也加入分隔符集合。这些变体均可在本实现基础上最小化改动。小结LeetCode 819 Most Common Word 是一道字符串处理 哈希表的入门题核心考点是正确的单词切分处理标点与大小写与统计—过滤—取极值的流程组织。仓库 LeetCode-Go 通过start指针手工分词的方式在单次线性遍历内同时完成了切词与计数实现简洁、无额外依赖并配有覆盖官方示例与空禁用列表两种场景的单元测试可作为该类型题目的标准参考答案。如需查看完整源码与文档可继续阅读 题解 README、核心实现 与 单元测试。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考