819. Most Common Word
Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 1
Acceptance rate: 45.5%
Problem Breakdown
The problem requires finding the most frequent non-banned word in a given paragraph. The words are case-insensitive, and punctuation should be ignored. The input consists of a string paragraph and an array of banned words banned. The output is the most frequent non-banned word in lowercase.
Inputs:
paragraph: A string containing English letters, spaces, or punctuation.banned: An array of strings representing banned words.
Outputs:
- A single string representing the most frequent non-banned word in lowercase.
Implicit Constraints/Edge Cases:
- The paragraph can contain punctuation adjacent to words.
- Words are case-insensitive.
- There is at least one non-banned word in the paragraph.
- The answer is guaranteed to be unique.
Intuition
A brute-force approach would involve:
- Splitting the paragraph into words while ignoring punctuation and converting them to lowercase.
- Counting the occurrences of each word, excluding banned words.
- Finding the word with the highest count.
This approach is inefficient because it involves multiple passes over the data and uses additional space for storing counts.
A better approach leverages a hash map (dictionary) to efficiently count word occurrences and another set for banned words. This reduces time complexity by allowing constant-time lookups for both counting and checking bans.
Approach
- Normalize the Paragraph: Convert the paragraph to lowercase and replace all punctuation with spaces.
- Split into Words: Use the
split()method to break the paragraph into individual words. - Count Non-Banned Words: Use a dictionary to count occurrences of each word that is not in the banned list.
- Find the Most Frequent Word: Iterate through the dictionary to find the word with the highest count.
Data Structures:
- Dictionary: To store word counts.
- Set: To store banned words for O(1) lookup time.
Complexity Analysis
- Time Complexity: O(n + m), where n is the length of the paragraph and m is the number of banned words. This accounts for splitting the paragraph, counting words, and finding the most frequent word.
- Space Complexity: O(n + m), for storing the dictionary of word counts and the set of banned words.
Solution
def mostCommonWord(paragraph: str, banned: List[str]) -> str:
# Normalize the paragraph by converting to lowercase and replacing punctuation with spaces
normalized_paragraph = ''.join([char.lower() if char.isalnum() else ' ' for char in paragraph])
# Split the paragraph into words
words = normalized_paragraph.split()
# Create a set of banned words for O(1) lookup time
banned_set = set(banned)
# Dictionary to store word counts
word_count = {}
# Count occurrences of each non-banned word
for word in words:
if word not in banned_set:
if word in word_count:
word_count[word] += 1
else:
word_count[word] = 1
# Find the most frequent non-banned word
most_frequent_word = max(word_count, key=word_count.get)
return most_frequent_word
Edge Cases Handled
- Punctuation Adjacent to Words: Replacing punctuation with spaces ensures words are correctly identified.
- Case Insensitivity: Converting the paragraph to lowercase handles case insensitivity.
- Empty Banned List: The code works correctly even if no words are banned.
- Unique Answer: The problem guarantees a unique answer, so the code does not need to handle ties.