题目难度: 中等

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

设计一个方法，找出任意指定单词在一本书中的出现频率。

你的实现应该支持如下操作：

• WordsFrequency(book)构造函数，参数为字符串数组构成的一本书
• get(word)查询指定单词在书中出现的频率

示例：

• WordsFrequency wordsFrequency = new WordsFrequency({"i", "have", "an", "apple", "he", "have", "a", "pen"});
• wordsFrequency.get("you"); //返回 0，"you"没有出现过
• wordsFrequency.get("have"); //返回 2，"have"出现 2 次
• wordsFrequency.get("an"); //返回 1
• wordsFrequency.get("apple"); //返回 1
• wordsFrequency.get("pen"); //返回 1

提示：

• book[i]中只包含小写字母
• 1 <= book.length <= 100000
• 1 <= book[i].length <= 10
• get 函数的调用次数不会超过 100000

题目思考

1. 使用什么数据结构可以高效得出频率?

解决方案

思路

• 要想快速得到单词频率, 很容易想到使用哈希表来实现: 键是单词, 值是其出现次数
• 所以只需要遍历输入字符串数组, 然后利用哈希表统计每个单词的次数即可
• 下面代码使用了 python3 内置的 collections.Counter, 一行即可

复杂度

• 时间复杂度 O(C): C 是单词的平均长度, 每次操作只需要从哈希表中找匹配的字符串即可
• 空间复杂度 O(NC): N 是单词数目, 需要存储所有单词的信息

代码

class WordsFrequency:
    def __init__(self, book: List[str]):
        self.cnts = collections.Counter(book)

    def get(self, word: str) -> int:
        return self.cnts[word]

大家可以在下面这些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊