819. Most Common Word

Problem Description

The problem requires that you find the most frequent word from a given string, paragraph, which is not included in a list of banned words, banned. The string paragraph can contain uppercase and lowercase letters. Finally, the result should be a lowercase word that occurs the most frequently in paragraph and is not present in the banned list. It is assured that there is at least one such word, and there is only one unique answer.

Intuition

The challenge is to accurately count word occurrences while excluding banned words and managing different cases (uppercase/lowercase). The approach involves several steps. First, normalize the paragraph by converting it to lowercase to ensure case insensitivity. Next, use regular expressions to extract words by ignoring punctuation and other non-alphabetic characters.

After the words have been extracted, use the Counter class from the collections library to count the frequency of each word. We then iterate through the most common words while skipping those present in the set of banned words. A set is used for the banned words to achieve O(1) lookup times.

By doing this, we ensure that the first word that appears in the most_common list and is not in the set of banned words is the answer, and we can then return this word as the most common non-banned word in the paragraph.

Solution Approach

The solution to the problem utilizes several Python features and data structures to approach the task efficiently:

1. Normalization of Text: First, we convert the entire paragraph to lowercase using the lower() method. This ensures that all words are counted in a case-insensitive manner.

2. Word Extraction: We then use the re.findall() function from the re module (which stands for "regular expression") to extract all the words in the text. The regular expression '[a-z]+' is used to match continuous sequences of lowercase letters ('a' to 'z'), effectively skipping over any punctuation or other characters.

3. Word Frequency Counting: Python's Counter class from the collections module is used to count the frequency of each word. This data structure is ideal for this use case because it allows for efficient counting and retrieval of the most common elements.

4. Set for Banned Words: The banned words are stored in a set, which allows us to check if a word is banned in constant time, thanks to the underlying hash table implementation of sets in Python.

5. Finding the Most Common Non-Banned Word: We use the most_common() method of the Counter class to get a list of words sorted by their frequency in descending order. The next() function, in conjunction with a generator expression, iterates through this list to find and retrieve the first word that is not present in the set of banned words.

The final line return next(word for word, _ in p.most_common() if word not in s) uses a generator expression to go through the words in the order of decreasing frequency and checks if the word is not in the banned set s. The underscore _ is used to ignore the frequency in the tuple returned by p.most_common() since we only care about the word itself in this context.

With the help of these tools and constructs, the solution efficiently finds the most frequent, non-banned word in the input paragraph.

Example Walkthrough

To illustrate the proposed solution approach, imagine you have the following paragraph and banned list:

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

Following the solution steps:

1. Normalization of Text: Convert the entire paragraph to lowercase.

   Result: "bob hit a ball, the hit ball flew far after it was hit."

2. Word Extraction: Use a regular expression to extract all the words.

   Code Example: re.findall(r'[a-z]+', "bob hit a ball, the hit ball flew far after it was hit.")

   Result: ['bob', 'hit', 'a', 'ball', 'the', 'hit', 'ball', 'flew', 'far', 'after', 'it', 'was', 'hit']

3. Word Frequency Counting: Use the Counter to count the frequency of each word.

   Code Example: Counter(['bob', 'hit', 'a', 'ball', 'the', 'hit', 'ball', 'flew', 'far', 'after', 'it', 'was', 'hit'])

   Result: Counter({'hit': 3, 'ball': 2, 'bob': 1, 'a': 1, 'the': 1, 'flew': 1, 'far': 1, 'after': 1, 'it': 1, 'was': 1})

4. Set for Banned Words: Create a set of the banned words.

   Result: {"hit"}

5. Finding the Most Common Non-Banned Word: Iterate through the list of most common words and return the first one that is not banned.

   Code Example: next(word for word, _ in Counter(['bob', 'hit', 'a', 'ball', 'the', 'hit', 'ball', 'flew', 'far', 'after', 'it', 'was', 'hit']).most_common() if word not in {"hit"})

   Result: 'ball'

So, in this example, ball would be the most frequent, non-banned word from the paragraph. It appears 2 times and is not included in the banned list.

Solution Implementation

Time and Space Complexity

The provided code snippet defines a function that returns the most common non-banned word from a string paragraph, ignoring words in the banned list banned. It utilizes regular expressions to identify words and the collections.Counter class to count occurrences.

Time Complexity

The time complexity of the mostCommonWord function is primarily determined by several operations:

1. re.findall: This function is used to find all substrings in paragraph that match the regular expression [a-z]+, effectively extracting all words composed of lowercase letters. The complexity of this operation is O(n), where n is the length of paragraph, as it must traverse the entire paragraph and perform pattern matching.

2. paragraph.lower(): Lowercasing the entire paragraph has a time complexity of O(n).

3. Counter.most_common: The Counter object is created from the list of words found using re.findall, which also has a complexity of O(m) where m is the number of words in the paragraph. The most_common method then sorts these word counts, which in the worst case is O(m log m) if the Counter implementation uses Timsort, a variation of sorting that has this worst-case complexity.

4. next with generator expression: In the worst case, we might need to iterate through all m words to find one that is not in the banned set. Checking if a word is in the banned set is O(1) due to using a set.

The overall time complexity T(n) therefore is dominated by the sorting step in Counter.most_common, which gives us:

T(n) = O(n) + O(n) + O(m) + O(m log m)

Since m, the number of unique words, is typically much less than n, we can consider O(n) as a more practical worst-case estimate for large paragraphs.

Space Complexity

The space complexity is also determined by several factors:

1. The set of banned words s: If there are b banned words, the space complexity for the set is O(b).

2. The counter p: In the worst case, if every word in paragraph is unique, the space needed for the counter would be O(m).

3. The list of words produced by re.findall: This list also has a space complexity of O(m) in the worst case.

Therefore, the total space complexity S(m, b) is a combination of the space needed for these data structures:

S(m, b) = O(b) + O(m) + O(m)

S(m, b) = O(m + b)

In conclusion, the mostCommonWord function has a time complexity of O(n) and a space complexity of O(m + b), where n is the length of paragraph, m is the number of unique words in the paragraph, and b is the number of banned words.

Learn more about how to find time and space complexity quickly using problem constraints.