819. Most Common Word

LeetCode original: C# #array #csharp #graph #hash-table #leetcode #sort #string #trie
Le texte du problème est traduit du russe pour la langue sélectionnée. Le code reste inchangé.
LeetCode Static

: easy

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

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

Exemple:

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

correspondant/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

brouillon automatique, à relire avant soumission 
#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

correspondant/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

correspondant/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

correspondant/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

offres actives with overlapping task tags are affichés.

Toutes les offres
Il n'y a pas encore d'offres actives.