819_Most Common Word

[easy] [string]

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"

Solution 1:

Idea:

• Split the paragraph into a list of words, get rid of all the white spaces and punctuations. (Replace all punctuations with white space, then split using white space, covert into lowercase.)

• Loop over each word, if it's not banned, store in a dictionary with its frequency.

• Return the word which has the max frequency.

Time Complexity: $O(n)$

Space Complexity: $O(n)$

def mostCommonWord(paragraph, banned):
    """
    :type paragraph: str
    :type banned: List[str]
    :rtype: str
    """

    # replace all punctuations with space
    for punc in string.punctuation:
        # string.punctuation is a string containing all punctuations
        paragraph = paragraph.replace(punc, " ")

    words = paragraph.lower().split()

    dict = {}
    banned = set(banned)
    for item in words:
        if item not in banned:
            dict[item] = dict.get(item, 0) + 1
    return max(dict.keys(), key=(lambda k: dict[k]))

Solution 2:

Idea:

• Initialize a dictionary to store all the words not in banned set.

• Initialize an empty string to store a word.

• Loop over each character in paragraph

  • If it's an alphabetic, append to the word

  • If it's not an alphabetic, word is not empty, check if word is in banned set. If not, add to the dictionary.

  • O.w. just skip to next

• In the last step, is word is not empty and not in banned set, add to dictionary.

• Return the key in the dictionary corresponding to the largest value.

Time Complexity: $O(n)$

Space Complexity: $O(n)$

def mostCommonWord(paragraph, banned):
    """
    :type paragraph: str
    :type banned: List[str]
    :rtype: str
    """

    word = ''
    dict = {}
    banned = set(banned)
    for c in paragraph:
        if c.isalpha() :
            word = word + c.lower()
        elif len(word) != 0:
            if word not in banned:
                dict[word] = dict.get(word, 0) + 1
            word = ''
    if len(word) != 0 and word not in banned:
        dict[word] = dict.get(word, 0) + 1
    return max(dict.keys(), key=(lambda k: dict[k]))