notes | Kisstar

# 面试题 16.02. 单词频率

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

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

  • 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：

可以深度递归字符串数组将单词出现的次数存储在 HashMap 中，之后查询时可以直接中 HashMap 中获取。

/**
 * @param {string[]} book
 */
var WordsFrequency = function(book) {
  this.wordMap = Object.create(null)

  const note = _book => {
    _book.forEach(word => {
      if (Array.isArray(word)) {
        note(word)
        return
      }

      if (this.wordMap[word]) {
        this.wordMap[word]++
      } else {
        this.wordMap[word] = 1
      }
    })
  }

  note(book)
}

/**
 * @param {string} word
 * @return {number}
 */
WordsFrequency.prototype.get = function(word) {
  return this.wordMap[word] || 0
}

解法 2：

将嵌套数组拉平为一维数组，获取指定单词的次数时在数组中刷选出对应的单词，然后通过读取结果数组的长度获取到次数。

/**
 * @param {string[]} book
 */
var WordsFrequency = function(book) {
  this.book = book.flat(Infinity)
}

/**
 * @param {string} word
 * @return {number}
 */
WordsFrequency.prototype.get = function(word) {
  return this.book.filter(item => item === word).length
}

# 参考

←