How do you solve Most Common Word on LeetCode?

Most Common Word (LeetCode #819) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Words are case-insensitive and punctuation should be ignored.

What is the brute force solution for Most Common Word?

The brute force approach for Most Common Word is Brute Force, with O(n²) time complexity and O(1) space complexity. In this approach, we will split the paragraph into words and check the frequency of each word. For each word, we will check if it is banned and keep track of the counts. This method is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Most Common Word?

Most Common Word uses the following concepts: Array, Hash Table, String, Counting. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Most Common Word?

Always clarify how to handle case sensitivity and punctuation with the interviewer. Discuss your thought process while coding to demonstrate your understanding. Consider edge cases, such as empty paragraphs or all words being banned.

What are common mistakes when solving Most Common Word?

Not converting words to lowercase, leading to case sensitivity issues. Failing to handle punctuation correctly, which can cause incorrect word counts.

#819

Most Common Word

Easy

ArrayHash TableStringCountingHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

This approach uses a hash map to count the occurrences of each word efficiently. By using a set for banned words, we can quickly check if a word is banned. This significantly reduces the time complexity.

⚙️

Algorithm

5 steps

1Step 1: Convert the paragraph to lowercase and extract words using regex to ignore punctuation.
2Step 2: Store banned words in a set for O(1) lookup.
3Step 3: Use a hash map to count occurrences of each word that is not banned.
4Step 4: Iterate through the hash map to find the word with the highest count.
5Step 5: Return that word.

solution.py15 lines

1# Full working Python code
2import re
3
4
5def most_common_word(paragraph, banned):
6    words = re.findall(r'\w+', paragraph.lower())
7    banned_set = set(banned)
8    count = {}
9    for word in words:
10        if word not in banned_set:
11            count[word] = count.get(word, 0) + 1
12    return max(count, key=count.get)
13
14# Example usage
15print(most_common_word("Bob hit a ball, the hit BALL flew far after it was hit.", ["hit"]))

ℹ

Complexity note: The time complexity is O(n) because we traverse the paragraph once to count the words, and the space complexity is O(n) due to the storage of the word counts.

1Words are case-insensitive and punctuation should be ignored.
2Using a hash map allows for efficient counting and retrieval of the most common word.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.