leetcode/lcci/16.02.Words Frequency

comments	difficulty	edit_url
true	Medium	https://github.com/doocs/leetcode/edit/main/lcci/16.02.Words%20Frequency/README_EN.md

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

Python3

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)

Java

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

C++

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

Go

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

TypeScript

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

Rust

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

JavaScript

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

Swift

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