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)\).

Python3JavaC++GoTypeScriptRustJavaScriptSwift

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)
    }
}

/**
 * @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)
 */

class WordsFrequency {
    private var cnt: [String: Int] = [:]

    init(_ book: [String]) {
        for word in book {
            cnt[word, default: 0] += 1
        }
    }

    func get(_ word: String) -> Int {
        return cnt[word, default: 0]
    }
}

16.02. Words Frequency

Description

Solutions

Solution 1: Hash Table

Comments