Solution Explanation for LeetCode 819: Most Common Word

This problem involves finding the most frequent word in a given paragraph, excluding a list of banned words. The solution involves several steps:

1. Preprocessing: Clean the input paragraph by converting it to lowercase and removing punctuation. This ensures case-insensitivity and avoids counting variations of the same word differently.

2. Word Counting: Count the occurrences of each word in the cleaned paragraph. A hash map (dictionary in Python) is ideal for this, storing words as keys and their counts as values.

3. Banned Word Filtering: Exclude words from the count that appear in the banned list. A set (or HashSet) is efficient for checking if a word is banned.

4. Finding the Most Frequent Word: Iterate through the word counts and identify the word with the highest count.

Time and Space Complexity Analysis:

• Time Complexity: O(N + M), where N is the length of the paragraph and M is the length of the banned list. The preprocessing step (cleaning the paragraph) takes O(N) time. Building the word count takes O(N) time in the average case (hash table lookups are typically O(1)). Checking if a word is banned takes O(1) on average using a set. Finally, finding the most frequent word takes O(N) in the worst case if we need to iterate over all words.
• Space Complexity: O(N), where N is the length of the paragraph. In the worst-case scenario (all words are unique and not banned), the hash map will store all unique words from the paragraph. The space for the banned words set is O(M). Therefore, the overall space complexity is dominated by O(N).

Code Examples:

The solutions below demonstrate different approaches using several programming languages. Note that some optimizations are used to improve efficiency, but the core logic remains consistent.

Python:

import re
from collections import Counter
 
class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        # Preprocessing: Convert to lowercase and remove punctuation
        cleaned_paragraph = re.sub(r'[^\w\s]', '', paragraph).lower()
 
        # Word Counting and Filtering
        word_counts = Counter(cleaned_paragraph.split())
        
        # Finding the Most Frequent Word (Efficiently using next)
        banned_set = set(banned)
        for word, count in word_counts.most_common():
            if word not in banned_set:
                return word

Java:

import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
 
class Solution {
    public String mostCommonWord(String paragraph, String[] banned) {
        // Preprocessing
        paragraph = paragraph.toLowerCase();
        Pattern p = Pattern.compile("[a-zA-Z]+"); // Matches only alphabetic words
        Matcher m = p.matcher(paragraph);
        Map<String, Integer> wordCounts = new HashMap<>();
        Set<String> bannedSet = new HashSet<>(Arrays.asList(banned));
 
        // Word Counting and Filtering
        while (m.find()) {
            String word = m.group();
            if (!bannedSet.contains(word)) {
                wordCounts.put(word, wordCounts.getOrDefault(word, 0) + 1);
            }
        }
 
        // Finding Most Frequent Word
        String mostFrequent = "";
        int maxCount = 0;
        for (Map.Entry<String, Integer> entry : wordCounts.entrySet()) {
            if (entry.getValue() > maxCount) {
                maxCount = entry.getValue();
                mostFrequent = entry.getKey();
            }
        }
        return mostFrequent;
    }
}

Other Languages: The core logic is similar across other languages (C++, Go, TypeScript, Rust) with variations in library usage and syntax. The provided solutions in the original response demonstrate those variations effectively. The key is to use efficient data structures (hash maps/dictionaries and sets) and appropriate string manipulation techniques.