Question

16.02. Words Frequency

中文文档

Description

Design a method to find the frequency of occurrences of any given word in a book. What if we were running this algorithm multiple times?

You should implement following methods:

• WordsFrequency(book) constructor, parameter is a array of strings, representing the book.
• get(word) get the frequency of word in the book. 

Example:

WordsFrequency wordsFrequency = new WordsFrequency({"i", "have", "an", "apple", "he", "have", "a", "pen"});

wordsFrequency.get("you"); //returns 0，"you" is not in the book

wordsFrequency.get("have"); //returns 2，"have" occurs twice in the book

wordsFrequency.get("an"); //returns 1

wordsFrequency.get("apple"); //returns 1

wordsFrequency.get("pen"); //returns 1

Note:

• There are only lowercase letters in book[i].
• 1 <= book.length <= 100000
• 1 <= book[i].length <= 10
• get function will not be called more than 100000 times.

Solutions

Solution 1: Hash Table

We use a hash table $cnt$ to count the number of occurrences of each word in $book$.

When calling the get function, we only need to return the number of occurrences of the corresponding word in $cnt$.

In terms of time complexity, the time complexity of initializing the hash table $cnt$ is $O(n)$, where $n$ is the length of $book$. The time complexity of the get function is $O(1)$. The space complexity is $O(n)$.

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

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


# Your WordsFrequency object will be instantiated and called as such:
# obj = WordsFrequency(book)
# param_1 = obj.get(word)

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

  public WordsFrequency(String[] book) {
    for (String x : book) {
      cnt.merge(x, 1, Integer::sum);
    }
  }

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

/**
 * Your WordsFrequency object will be instantiated and called as such:
 * WordsFrequency obj = new WordsFrequency(book);
 * int param_1 = obj.get(word);
 */

class WordsFrequency {
public:
  WordsFrequency(vector<string>& book) {
    for (auto& x : book) {
      ++cnt[x];
    }
  }

  int get(string word) {
    return cnt[word];
  }

private:
  unordered_map<string, int> cnt;
};

/**
 * Your WordsFrequency object will be instantiated and called as such:
 * WordsFrequency* obj = new WordsFrequency(book);
 * int param_1 = obj->get(word);
 */

type WordsFrequency struct {
  cnt map[string]int
}

func Constructor(book []string) WordsFrequency {
  cnt := map[string]int{}
  for _, x := range book {
    cnt[x]++
  }
  return WordsFrequency{cnt}
}

func (this *WordsFrequency) Get(word string) int {
  return this.cnt[word]
}

/**
 * Your WordsFrequency object will be instantiated and called as such:
 * obj := Constructor(book);
 * param_1 := obj.Get(word);
 */

class WordsFrequency {
  private cnt: Map<string, number>;

  constructor(book: string[]) {
    const cnt = new Map<string, number>();
    for (const word of book) {
      cnt.set(word, (cnt.get(word) ?? 0) + 1);
    }
    this.cnt = cnt;
  }

  get(word: string): number {
    return this.cnt.get(word) ?? 0;
  }
}

/**
 * Your WordsFrequency object will be instantiated and called as such:
 * var obj = new WordsFrequency(book)
 * var param_1 = obj.get(word)
 */

use std::collections::HashMap;
struct WordsFrequency {
  cnt: HashMap<String, i32>,
}

/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl WordsFrequency {
  fn new(book: Vec<String>) -> Self {
    let mut cnt = HashMap::new();
    for word in book.into_iter() {
      *cnt.entry(word).or_insert(0) += 1;
    }
    Self { cnt }
  }

  fn get(&self, word: String) -> i32 {
    *self.cnt.get(&word).unwrap_or(&0)
  }
}/**
 * Your WordsFrequency object will be instantiated and called as such:
 * let obj = WordsFrequency::new(book);
 * let ret_1: i32 = obj.get(word);
 */

/**
 * @param {string[]} book
 */
var WordsFrequency = function (book) {
  this.cnt = new Map();
  for (const x of book) {
    this.cnt.set(x, (this.cnt.get(x) || 0) + 1);
  }
};

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

/**
 * Your WordsFrequency object will be instantiated and called as such:
 * var obj = new WordsFrequency(book)
 * var param_1 = obj.get(word)
 */