Given a paragraph and a list of banned words, return the most frequent word that is not in the list of banned words. It is guaranteed there is at least one word that isn't banned, and that the answer is unique.
Words in the list of banned words are given in lowercase, and free of punctuation. Words in the paragraph are not case sensitive. The answer is in lowercase.
Example:
Input: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit." banned = ["hit"] Output: "ball" Explanation: "hit" occurs 3 times, but it is a banned word. "ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. Note that words in the paragraph are not case sensitive, that punctuation is ignored (even if adjacent to words, such as "ball,"), and that "hit" isn't the answer even though it occurs more because it is banned.
Note:
1 <= paragraph.length <= 1000.0 <= banned.length <= 100.1 <= banned[i].length <= 10.paragraph may have uppercase symbols, and even if it is a proper noun.)paragraph only consists of letters, spaces, or the punctuation symbols !?',;.
The description was taken from https://leetcode.com/problems/most-common-word/.
#O(P+B) Time for the size of paragraph and banned, O(P) Space for count of paragraph wordsclass Solution: def mostCommonWord(self, paragraph: str, banned: List[str]) -> str: for char in "?!';,.": paragraph = paragraph.replace(char, " ") seen = {} highest_count = 0 paragraph = paragraph.lower().split() for word in paragraph: if word in banned: continue elif word in seen: seen[word] += 1 else: seen[word] = 1 if seen[word] > highest_count: highest_count = seen[word] most_common = word return most_commonThe problem description requires us to count the frequency of each non-banned word, so utilizing a hashmap or a built-in counter is a good approach. What we will do first is go through the paragraph and remove the punctuation marks then convert everything to lowercase to clean the data. Next, we will make a second pass through the paragraph, and if the current word is not in the list of banned words, we will add or increment it within our hashmap. We will use a running sum to continuously check the highest count word in our dictionary and we will return it once we have finished with the second traversal.
We’ll start by replacing all of the punctuation marks in the paragraph with empty space so that when we split the string later, we will know where to break apart the words.
for char in "?!';,.": paragraph = paragraph.replace(char, " ")
Next, let's initialize our dictionary which will count how many times we have seen a word. We will also initialize our highest count to zero.
seen = {} highest_count = 0
Afterward, we will convert our paragraph to all lowercase characters and split it into an array of strings so that we have a clean list of words to iterate through.
paragraph = paragraph.lower().split()
We will then traverse this array of strings we just created and see if the word we’re currently looking at is in the string of banned words. If it is, we will continue to the next word.
for word in paragraph: if word in banned: continue
If the word is not banned then we will check if we have already seen this word. If we have, we’ll increment its frequency value.
elif word in seen: seen[word] += 1
If it isn’t then we’ll put it there and set its count to one, since we have seen it once so far.
else: seen[word] = 1
Next, we’ll see if the count of the current word is higher than our highest saved count.
if seen[word] > highest_count:
If it is, we’ll update the highest count to the frequency of the current word and save the current word as the most common.
highest_count = seen[word] most_common = word
We’ll repeat this until we have reached the end of the paragraph array at which point we will return the word with the highest frequency of occurences.
return most_common