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

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

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 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 中的禁用单词；  
② 为了方便后续的判断，定义如下变量或类：

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

③ 开始遍历 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;
        }
    }