819. Most Common Word

LeetCode original: C# #array #csharp #graph #hash-table #leetcode #sort #string #trie

Task text is translated from Russian for the selected interface language. Code is left unchanged.

LeetCode Static

: easy

Дана string paragraph и array строк banned, представляющий запрещенные слова. return наиболее часто встречающееся слово, которое не запрещено. Гарантируется, что существует хотя бы одно слово, которое не запрещено, и что ответ является уникальным.

Слова в paragraph нечувствительны к регистру, и ответ должен быть возвращен в нижнем регистре.

Example:

Input: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.", banned = ["hit"]

Output: "ball"

Explanation:

"hit" occurs 3 times, but it is a banned word.

"ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph.

Note that words in the paragraph are not case sensitive,

that punctuation is ignored (even if adjacent to words, such as "ball,"),

and that "hit" isn't the answer even though it occurs more because it is banned.

C# solution

matched/original

public class Solution {
    public string MostCommonWord(string paragraph, IList<string> banned) {
        string normalizedStr = new string(paragraph.Select(c => char.IsLetterOrDigit(c) ? char.ToLower(c) : ' ').ToArray());
        string[] words = normalizedStr.Split(new char[] {' '}, StringSplitOptions.RemoveEmptyEntries);
        var wordCount = new Dictionary<string, int>();
        var bannedWords = new HashSet<string>(banned);
        foreach (string word in words) {
            if (!bannedWords.Contains(word)) {
                if (!wordCount.ContainsKey(word)) {
                    wordCount[word] = 0;
                }
                wordCount[word]++;
            }
        }
        return wordCount.OrderByDescending(kv => kv.Value).First().Key;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public string MostCommonWord(string paragraph, vector<string> banned) {
        string normalizedStr = new string(paragraph.Select(c => char.IsLetterOrDigit(c) ? char.ToLower(c) : ' ').ToArray());
        vector<string> words = normalizedStr.Split(new char[] {' '}, StringSplitOptions.RemoveEmptyEntries);
        var wordCount = new unordered_map<string, int>();
        var bannedWords = new HashSet<string>(banned);
        foreach (string word in words) {
            if (!bannedWords.Contains(word)) {
                if (!wordCount.count(word)) {
                    wordCount[word] = 0;
                }
                wordCount[word]++;
            }
        }
        return wordCount.OrderByDescending(kv => kv.Value).First().Key;
    }
}

Java solution

matched/original

class Solution {
    public String mostCommonWord(String paragraph, List<String> banned) {
        String normalizedStr = paragraph.replaceAll("[^a-zA-Z0-9 ]", " ").toLowerCase();
        String[] words = normalizedStr.split("\\s+");
        Map<String, Integer> wordCount = new HashMap<>();
        Set<String> bannedWords = new HashSet<>(banned);

        for (String word : words) {
            if (!bannedWords.contains(word)) {
                wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
            }
        }

        return Collections.max(wordCount.entrySet(), Map.Entry.comparingByValue()).getKey();
    }

Python solution

matched/original

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        normalized_str = ''.join([c.lower() if c.isalnum() else ' ' for c in paragraph])
        words = normalized_str.split()
        word_count = defaultdict(int)
        banned_words = set(banned)
        
        for word in words:
            if word not in banned_words:
                word_count[word] += 1

Go solution

matched/original

func mostCommonWord(paragraph string, banned []string) string {
    normalizedStr := strings.Map(func(r rune) rune {
        if unicode.IsLetter(r) || unicode.IsDigit(r) {
            return unicode.ToLower(r)
        }
        return ' '
    }, paragraph)

    words := strings.Fields(normalizedStr)
    wordCount := make(map[string]int)
    bannedWords := make(map[string]bool)

    for _, word := range banned {
        bannedWords[word] = true
    }

    for _, word := range words {
        if !bannedWords[word] {
            wordCount[word]++
        }
    }

    maxWord := ""
    maxCount := 0
    for word, count := range wordCount {
        if count > maxCount {
            maxWord = word
            maxCount = count
        }
    }

    return maxWord
}

Algorithm

Заменяем всю пунктуацию пробелами и одновременно переводим каждую букву в нижний регистр. Это можно сделать и в два этапа, но здесь мы объединяем их в один этап.

Разбиваем полученный результат на слова, используя пробелы в качестве разделителей.

Затем итерируемся по словам, чтобы подсчитать количество появлений каждого уникального слова, исключая слова из списка запрещенных. С помощью хеш-таблицы {слово->количество} проходим по всем elementам, чтобы find слово с наивысшей частотой.

😎

Vacancies for this task

Active vacancies with overlapping task tags are shown.

All vacancies

There are no active vacancies yet.