LeetCode_哈希表_哈希集合_简单_819.最常见的单词-蒲公英云

LeetCode_哈希表_哈希集合_简单_819.最常见的单词

短命女 2023-10-07 00:24 134阅读 0赞

1.题目

给定一个段落 (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 <= 段落长度 <= 1000
0 <= 禁用单词个数 <= 100
1 <= 禁用单词长度 <= 10
答案是唯一的, 且都是小写字母 (即使在 paragraph 里是大写的，即使是一些特定的名词，答案都是小写的。)
paragraph 只包含字母、空格和下列标点符号!?',;.
不存在没有连字符或者带有连字符的单词。
单词里只包含字母，不会出现省略号或者其他标点符号。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/most-common-word

2.思路

（1）哈希表 & 哈希集合
① 为了方便判断 paragraph 中的单词是在 banned 中，所以可以使用哈希集合 bannedSet 来保存 banned 中的禁用单词；
② 为了方便后续的判断，定义如下变量或类：

maxFrequency	记录 paragraph 中非禁用单词的最大出现次数，初始值为 0
frequencies	是一个哈希表，用于保存 paragraph 中的非禁用单词以及对应出现的次数
builder	StringBuilder 对象，用于保存遍历 paragraph 中遇到的每个单词

③ 开始遍历 paragraph：
1）如果当前字符是英文字母，则将其转化为小写字母后保存到 builder 中；
2）如果当前字符不是英文字母，那么设 word 为 builder 中的所有字符所组成的单词，如果 word 不在 bannedSet 中，则将其存入 frequencies 中，同时更新 maxFrequency，最后再清空 builder，以便存储下一个单词；

④ 遍历 paragraph 结束后，再遍历 frequencies 中的键值对，使用变量 res 保存出现次数为 maxFrequency 所对应的单词，最后再返回 res。

3.代码实现（Java）

//思路1————哈希表 & 哈希集合
class Solution {
    public String mostCommonWord(String paragraph, String[] banned) {
        Set<String> bannedSet = new HashSet<String>();
        for (String bannnedWord : banned) {
            bannedSet.add(bannnedWord);
        }
        // maxFrequency 记录 paragraph 中非禁用单词的最大出现次数，初始值为 0
        int maxFrequency = 0;
        // frequencies 保存 paragraph 中的非禁用单词以及对应出现的次数
        Map<String, Integer> frequencies = new HashMap<String, Integer>();
        // builder 用于保存遍历 paragraph 中遇到的每个单词
        StringBuilder builder = new StringBuilder();
        int length = paragraph.length();
        for (int i = 0; i <= length; i++) {
            if (i < length && Character.isLetter(paragraph.charAt(i))) {
                builder.append(Character.toLowerCase(paragraph.charAt(i)));
            } else if (builder.length() > 0) {
                String word = builder.toString();
                //如果 word 不是禁用列表中的单词，则将其存入 frequencies 中，同时更新 maxFrequency
                if (!bannedSet.contains(word)) {
                    int frequency = frequencies.getOrDefault(word, 0) + 1;
                    frequencies.put(word, frequency);
                    maxFrequency = Math.max(maxFrequency, frequency);
                }
                builder.setLength(0);
            }
        }
        String res = "";
        for (Map.Entry<String, Integer> entry : frequencies.entrySet()) {
            if (entry.getValue() == maxFrequency) {
                res = entry.getKey();
                break;
            }
        }
        return res;
    }
}