网络异常，图片无法展示
|
题目描述
这是 LeetCode 上的 819. 最常见的单词 ，难度为 简单。
Tag : 「模拟」、「哈希表」
给定一个段落 (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 <= `段落长度` <= 10001<=‘段落长度‘<=1000
- 0 <= `禁用单词个数` <= 1000<=‘禁用单词个数‘<=100
- 1 <= `禁用单词长度` <= 101<=‘禁用单词长度‘<=10
- 答案是唯一的, 且都是小写字母 (即使在
paragraph里是大写的，即使是一些特定的名词，答案都是小写的。) paragraph只包含字母、空格和下列标点符号!?',;.- 不存在没有连字符或者带有连字符的单词。
- 单词里只包含字母，不会出现省略号或者其他标点符号。
模拟
根据题意进行模拟即可。
代码：
class Solution { public String mostCommonWord(String s, String[] banned) { Set<String> set = new HashSet<>(); for (String b : banned) set.add(b); char[] cs = s.toCharArray(); int n = cs.length; String ans = null; Map<String, Integer> map = new HashMap<>(); for (int i = 0; i < n; ) { if (!Character.isLetter(cs[i]) && ++i >= 0) continue; int j = i; while (j < n && Character.isLetter(cs[j])) j++; String sub = s.substring(i, j).toLowerCase(); i = j + 1; if (set.contains(sub)) continue; map.put(sub, map.getOrDefault(sub, 0) + 1); if (ans == null || map.get(sub) > map.get(ans)) ans = sub; } return ans; } } 复制代码
- 时间复杂度：O(n + m)O(n+m)，nn 和 mm 分别代表
s的字符总长度和banned的字符总长度（哈希函数的计算与长度成正比） - 空间复杂度：O(n + m)O(n+m)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.819 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
