LeetCode 面试题 16.02. 单词频率

约 8 分钟
文章信息 7 个分类 5 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 华为 程序员面试金典（第 6 版）
标签
数组 字符串 哈希表 设计 字典树
目录

题目描述

✅ 面试题 16.02. 单词频率

题意分析

设计一个类 WordsFrequency，构造时接收一本"书"（一个字符串数组 book），之后要支持任意多次 get(word) 调用，每次返回该单词在书中出现的次数；单词不存在时返回 0。

约束里最重要的信号藏在接口形状里：构造函数只调用一次，get 会被调用很多次，而且书的内容在构造之后不再改变。这是典型的"一次预处理、多次查询"的静态数据结构题——出题人想看的是你能否把代价从查询侧挪到构造侧。题目提示里也明确写了"你可以假设 get 方法会被调用很多次"，等于把答案的方向直接告诉你了。

边界上要覆盖：查询一个从未出现过的单词（必须返回 0 而不是抛异常或返回 -1）；book 为空数组；同一个单词在书中重复出现多次；以及单词是按原字符串精确匹配的——本题不涉及大小写归一化、不做标点剥离，任何"顺手 toLowerCase"的自作主张都会改变语义。

解法：哈希表统计词频（构造一次，多次查询）

核心思路

最朴素的实现是把 book 原样存下来，每次 get(word) 时遍历一遍数组数出现次数。瓶颈很明显：单次查询 $O(n \cdot L)$，q 次查询就是 $O(qnL)$，而且每次查询都在重复做同一件事——同一个单词问两遍，第二遍的计数过程和第一遍一模一样，全是浪费。

关键观察是：书的内容在构造之后就不再变化，因此"每个单词出现多少次"这个答案在构造完成的那一刻就已经确定了。既然答案是静态的，就应该在构造时一次性把所有答案算好存起来，让 get 退化成一次查表。

由此确定要维护的状态：一张哈希表 freq，键是单词、值是它在 book 中出现的次数。不变量是：对任意字符串 w，freq 中 w 的值恒等于 w 在 book 里出现的次数；未出现的单词不在表中，查询时按"缺省值 0"处理。构造时对 book 做一次遍历，每读到一个单词就把它的计数加一，遍历结束不变量即成立；此后表不再变化，所以每次 get 都能直接读到正确答案。

这里刻意用哈希表而不是字典树（Trie），是因为本题的查询是整词精确匹配，哈希表单次查询是期望 $O(L)$（一次哈希 + 一次比较），常数比逐字符下行的 Trie 更小、代码也短得多。Trie 的优势在于前缀相关的查询（"有多少单词以 abc 开头"），本题用不上；但如果面试官追问"如果还要支持按前缀统计词频呢"，那就该换 Trie，在每个节点上额外维护经过该节点的单词计数。

解题步骤

  • 构造函数里建一张空哈希表，然后遍历 book 一次。遍历必须放在构造函数里而不是 get 里，这是整题的核心决策——把 $O(n)$ 的代价付一次，换取后续所有查询都是 $O(1)$ 级别。
  • 对每个单词执行"取出旧值加一再写回"。Java 写成 freq.put(word, freq.getOrDefault(word, 0) + 1)：getOrDefault 把"首次出现"和"重复出现"统一成同一行代码，不必写 containsKey 分支。Go 里 f[w]++ 更简洁，因为 map 读取缺失键时返回值类型的零值 0，自增后写回恰好就是 1。
  • get(word) 只做一次查表，并对缺失键返回 0。Java 用 freq.getOrDefault(word, 0)，Go 直接 wf.freq[word]（缺失键天然返回 0）。绝对不能在 get 里做任何遍历或计算，否则前面的预处理就白做了。
  • 返回值语义要和题目对齐：单词不存在时返回 0，而不是 -1 或抛异常。哈希表的"缺省零值"恰好就是正确答案，这是一个可以白拿的便利。

以 book = ["i", "have", "an", "apple", "he", "have", "a", "pen"] 走一遍：

构造阶段逐个处理：读到 "i"，表中没有，取默认 0 加一写回，freq = {i:1}；读到 "have"，freq = {i:1, have:1}；读到 "an"，freq = {i:1, have:1, an:1}；读到 "apple"，加入；读到 "he"，加入；读到第二个 "have"，此时表中已有值 1，取出加一写回 2，freq 中 have 变成 2；读到 "a"，加入（注意 "a" 和 "an" 是两个不同的键，哈希表按整串匹配，不会互相干扰）；读到 "pen"，加入。最终 freq = {i:1, have:2, an:1, apple:1, he:1, a:1, pen:1}。

查询阶段：get("have") 一次查表命中，返回 2，正确。get("an") 返回 1。get("apple") 返回 1。get("orange") 表中没有这个键，走缺省分支返回 0，正确——如果这里写成 freq.get(word) 而不带缺省，Java 会返回 null 并在拆箱成 int 时抛 NPE。

再验证一次预处理的价值：如果对这本书做 $10^5$ 次查询，遍历法要做 $10^5 \times 8$ 次字符串比较，而哈希表法只在构造时做 8 次插入，之后每次查询都是常数级——这就是"代价前移"的收益。

代码实现

class WordsFrequency {
    private final Map<String, Integer> freq = new HashMap<>();

    public WordsFrequency(String[] book) {
        for (String word : book) {
            freq.put(word, freq.getOrDefault(word, 0) + 1);
        }
    }

    public int get(String word) {
        return freq.getOrDefault(word, 0);
    }
}

type WordsFrequency struct {
    freq map[string]int
}

func Constructor(book []string) WordsFrequency {
    f := make(map[string]int)
    for _, w := range book {
        f[w]++
    }
    return WordsFrequency{freq: f}
}

func (wf *WordsFrequency) Get(word string) int {
    return wf.freq[word]
}

复杂度分析

  • 时间复杂度：构造是 $O(\sum w_i )$，即书中所有单词长度之和——每个单词被读一次并计算一次哈希；get 是期望 $O( word )$，一次哈希加一次相等比较，与书的规模 n 完全无关。相比之下暴力遍历法的 get 是 $O(n \cdot L)$。
  • 空间复杂度：$O(\sum w_i )$，最坏情况（所有单词互不相同）哈希表要存下全部单词及其计数；若重复很多，实际占用会小于这个上界。

关键点总结

  • "构造一次、查询多次"的接口形状，就是在提示把代价前移。看到设计题先数一下各接口的调用频次比例，把高频接口的复杂度压到最低，代价挪给低频接口，这是所有静态数据结构设计的第一原则。
  • 哈希表的缺省零值能免费处理"不存在"的边界。用 getOrDefault(key, 0) 或 Go map 的零值语义，比写 containsKey 分支更短也更不容易漏；前提是题目要求的缺省返回值恰好是零值，否则仍要显式指定。
  • 精确匹配用哈希表，前缀相关才用 Trie。两者不是"高级 / 低级"的关系，而是查询形态决定的：整词查询哈希表常数更小，前缀统计、通配匹配才轮到 Trie。选错会被追问"为什么这里需要 Trie"。
  • 不要顺手做题目没要求的归一化。大小写转换、去标点、trim 都会改变匹配语义；题目说按原字符串匹配就照做，需要归一化时应先向面试官确认。
  • 面试视角：主动给出"如果书会动态更新"和"如果要查前缀词频"两个延伸。前者只需再开一个 add(word) 方法同步更新计数，仍是 $O(1)$；后者需要换成 Trie，在每个节点维护"经过此节点的单词数"。能主动铺开这两条，说明你理解的是模型而不是这一道题。

易错点总结

  • 错误写法：把统计逻辑写在 get 里，构造函数只存下 book → 用例：一本 $10^4$ 个单词的书，做 $10^4$ 次查询：总代价 $10^8$ 次字符串比较，直接 TLE；而且完全违背了题目"get 会被调用很多次"的提示。
  • 错误写法：Java 里 get 写成 return freq.get(word); → 用例 get("orange")（书中没有这个词）：HashMap.get 返回 null，拆箱成 int 时抛 NullPointerException，正确答案是 0。
  • 错误写法：get 里写 if (!freq.containsKey(word)) return -1; → 用例 get("orange")：返回 -1，但题目要求不存在时返回 0，判题直接 WA。
  • 错误写法：构造时写 freq.put(word, 1)（直接赋值而非累加） → 用例 book = ["a", "a", "a"]、get("a")：每次都被覆盖成 1，返回 1，正确答案是 3。
  • 错误写法：构造时用 freq.putIfAbsent(word, freq.getOrDefault(word, 0) + 1) → 用例 book = ["a", "a"]：第二次因为键已存在而被跳过，计数停在 1，正确答案是 2。putIfAbsent 的语义是"缺失才写"，与累加相矛盾。
  • 错误写法：构造时顺手 word.toLowerCase() 归一化 → 用例 book = ["Apple", "apple"]、get("Apple")：两个不同的单词被合并，返回 2，正确答案是 1。题目要求按原字符串精确匹配。
  • 错误写法：用 String[] 加线性查找代替哈希表，理由是"数据量小" → 用例：书里有 $10^4$ 个不同单词、查询 $10^4$ 次：退化成 $10^8$ 量级；即使能过，面试里也会被要求换成哈希表并解释复杂度。
  • 错误写法：Go 里 Constructor 返回 WordsFrequency{} 而忘了 make(map[string]int) → 用例：构造后立刻 Get("a")：读一个 nil map 返回零值 0 恰好不崩，但构造阶段的 f[w]++ 会因为向 nil map 写入而 panic（assignment to entry in nil map）。map 必须显式初始化。
  • 错误写法：Go 里 Get 用值接收者且内部尝试懒初始化 map → 用例：任何查询：修改的是副本，主对象的 map 仍是 nil，下次查询又要重来。凡涉及修改字段的方法必须用指针接收者。
  • 错误写法：为了"省空间"只存出现次数大于 1 的单词 → 用例 book = ["a", "b"]、get("a")：a 只出现一次被剔除，查询返回 0，正确答案是 1。哈希表的键集合必须与书中出现过的单词集合完全一致。
  • 错误写法：改用 Trie 但只在叶子节点存计数，查询时走到中间节点就返回该节点的值 → 用例 book = ["a", "an"]、get("a")：若没有用独立的"单词结束"标记区分，"a" 这个前缀节点上的计数可能把 "an" 也算进去，返回 2，正确答案是 1。Trie 做词频必须区分"经过此节点"和"以此节点结尾"两个计数。

相似题目

题目 难度 考察点
706. 设计哈希映射 简单 反过来要求手写哈希表本身，考的是拉链法与冲突处理
692. 前K个高频单词 中等 统计词频只是第一步，重点在按"频次降序 + 字典序升序"选出前 K
208. 实现 Trie (前缀树) 中等 查询形态换成前缀匹配，哈希表失效，必须逐字符建树
49. 字母异位词分组 中等 键不再是原串而是排序后的签名，考的是"如何设计哈希键"
面试题 17.11. 单词距离 中等 同样是一次预处理多次查询，但要存下标列表并用双指针求最近距离