Most Common Word - Leetcode Solution

Problem Statement:

Given a paragraph and a list of banned words, find the most frequent word that is not in the list of banned words. It is assumed that the paragraph does not contain any punctuation except for spaces between words.

Example:

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

Output: "ball"

Explanation: The word "hit" is banned, so it does not count. The word "ball" occurs twice (once in uppercase and once in lowercase), making it the most frequent word in the paragraph.

Solution:

We can approach this problem in the following steps:

1. Convert the entire paragraph to lowercase to ensure that we are not counting the same word in different cases as separate words.

2. Split the paragraph into individual words using the whitespace as a delimiter.

3. Create a dictionary to keep track of the frequency of each word that is not in the list of banned words.

4. Iterate through each word in the paragraph and increment its count in the dictionary if it is not in the banned list.

5. Return the word with the highest frequency count from the dictionary.

Here is the Python code to implement this solution:

class Solution: def mostCommonWord(self, paragraph: str, banned: List[str]) -> str: # Step 1: Convert paragraph to lowercase paragraph = paragraph.lower()

    # Step 2: Split paragraph into individual words
    words = paragraph.split()
    
    # Step 3: Create dictionary to store word frequency
    word_count = {}
    
    # Step 4: Iterate through each word and update frequency count in dictionary
    for word in words:
        # Remove any punctuation from the word
        word = word.strip("!?',;.")
        if word not in banned:
            if word in word_count:
                word_count[word] += 1
            else:
                word_count[word] = 1
    
    # Step 5: Find word with highest frequency count in the dictionary
    most_common_word = ""
    max_count = 0
    for word, count in word_count.items():
        if count > max_count:
            most_common_word = word
            max_count = count
    
    return most_common_word

Time Complexity: O(N + M), where N is the length of the paragraph and M is the length of the banned list.

Space Complexity: O(N), since we store the frequency count of each word in a dictionary that can potentially contain N distinct words.

Overall, this is an efficient solution that should be able to handle large inputs without any issues.

1