【算法千题案例】每日LeetCode打卡——97.最常见的单词

呆呆敲代码的小Y

发布于 2021-12-27 08:30:27

5660

发布于 2021-12-27 08:30:27

文章被收录于专栏：呆呆敲代码的小Y 公众号

前言
- 原题样例：最常见的单词
  - C#方法：字典
  - Java 方法：简单计数
- 总结

前言

算法题

每天打卡一道算法题，既是一个学习过程，又是一个分享的过程
提示：本专栏解题编程语言一律使用 C# 和 Java 两种进行解题
要保持一个每天都在学习的状态，让我们一起努力成为算法大神吧
今天是力扣算法题持续打卡第97天

算法题

原题样例：最常见的单词

给定一个段落 (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 只包含字母、空格和下列标点符号!?’,;.
不存在没有连字符或者带有连字符的单词。
单词里只包含字母，不会出现省略号或者其他标点符号。

C#方法：字典

使用字典对数据进行处理，最后再判断是不是属于禁用词语中！

代码：

public class Solution {
    public string MostCommonWord(string paragraph, string[] banned) {

            paragraph =paragraph.ToLower();
            string str = "";
            Dictionary<string, int> dic = new Dictionary<string, int>();
            for (int i = 0; i < paragraph.Length; i++)
            {
                if (paragraph[i]-'a'<0|| paragraph[i] -'a' >26)
                {
                    if (string.IsNullOrEmpty(str))
                    {
                        continue;
                    }
                    else
                    {
                        if (dic.ContainsKey(str))
                        {
                            dic[str]++;
                        }
                        else
                        {
                            dic.Add(str,1);
                        }
                        str = "";
                    }
                }
                else
                {
                    str += paragraph[i].ToString();
                }
            }
             if (str!=""&&dic.ContainsKey(str))
             {
                dic[str]++;
             }
                else
             {
                dic.Add(str,1);
             }
               str = "";            
            int num = int.MinValue;
            string res = "";
            foreach (var item in dic)
            {
                if (banned.Contains(item.Key))
                {
                    continue;
                }
                else
                {
                    if (item.Value>num)
                    {
                        num = item.Value;
                        res = item.Key;
                    }
                }
            }
            return res;
    }
}

执行结果

通过
执行用时：112 ms，在所有 C# 提交中击败了58.00%的用户
内存消耗：39.9 MB，在所有 C# 提交中击败了58.33%的用户

Java 方法：简单计数

思路解析 我们统计出每个单词出现的次数，忽略所有的标点符号和大小写，答案即为出现次数最多且不在禁用列表中的那个单词。

统计单词的方法有两种。在第一种方法中，我们首先对整个段落按照空格进行分词（split），然后对于分出的每个单词，我们移除标点符号并忽略大小写。在第二种方法中，我们逐字符扫描整个段落，如果遇到一个非字母的符号，那就把之前遇到的字母作为一个单词。

对于每一个单词，我们会放入哈希映射（Java 中的 HashMap 或者 Python 中的 Counter）中进行计数。在每次放入单词之后，如果这个单词不在禁用列表中，我们就可以更新一次答案。

代码：

class Solution {
    public String mostCommonWord(String paragraph, String[] banned) {
        paragraph += ".";

        Set<String> banset = new HashSet();
        for (String word: banned) banset.add(word);
        Map<String, Integer> count = new HashMap();

        String ans = "";
        int ansfreq = 0;

        StringBuilder word = new StringBuilder();
        for (char c: paragraph.toCharArray()) {
            if (Character.isLetter(c)) {
                word.append(Character.toLowerCase(c));
            } else if (word.length() > 0) {
                String finalword = word.toString();
                if (!banset.contains(finalword)) {
                    count.put(finalword, count.getOrDefault(finalword, 0) + 1);
                    if (count.get(finalword) > ansfreq) {
                        ans = finalword;
                        ansfreq = count.get(finalword);
                    }
                }
                word = new StringBuilder();
            }
        }

        return ans;
    }
}

执行结果

通过
执行用时：5 ms，在所有 Java  提交中击败了98.76%的用户
内存消耗：38.2 MB，在所有 Java 提交中击败了88.29%的用户

复杂度分析

时间复杂度：O( P+B )
空间复杂度：O(P+B)

总结

今天是力扣算法题打卡的第九十七天！
文章采用 C#和 Java 两种编程语言进行解题
一些方法也是参考力扣大神写的，也是边学习边分享，再次感谢算法大佬们
那今天的算法题分享到此结束啦，明天再见！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/12/25 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

java

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

java

登录后参与评论

0 条评论

热度