Skip to content

819. Most Common Word 👎

  • Time: $O(|\texttt{paragraph}|)$
  • Space: $O(|\texttt{paragraph}| + |\texttt{banned}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
 public:
  string mostCommonWord(string paragraph, vector<string>& banned) {
    string ans;
    int maxCount = 0;
    unordered_map<string, int> count;
    unordered_set<string> bannedSet{banned.begin(), banned.end()};

    // Make the paragraph lowercased and remove all the punctuations.
    for (char& c : paragraph)
      c = isalpha(c) ? tolower(c) : ' ';

    istringstream iss(paragraph);

    for (string word; iss >> word;)
      if (!bannedSet.count(word))
        ++count[word];

    for (const auto& [word, freq] : count)
      if (freq > maxCount) {
        maxCount = freq;
        ans = word;
      }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
  public String mostCommonWord(String paragraph, String[] banned) {
    Pair<String, Integer> ans = new Pair<>("", 0);
    Set<String> bannedSet = new HashSet<>(Arrays.asList(banned));
    Map<String, Integer> count = new HashMap<>();
    String[] words = paragraph.replaceAll("\\W+", " ").toLowerCase().split("\\s+");

    for (final String word : words)
      if (!bannedSet.contains(word))
        if (count.merge(word, 1, Integer::sum) > ans.getValue())
          ans = new Pair<>(word, count.get(word));

    return ans.getKey();
  }
}

1
2
3
4
5
class Solution:
  def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
    banned = set(banned)
    words = re.findall(r'\w+', paragraph.lower())
    return collections.Counter(word for word in words if word not in banned).most_common(1)[0][0]