Most Common Word solution using TypeScript
Below is my TypeScript solution to the LeetCode "Most Common Word" question.
Algorithm: This solution finds the most common word while only needing to iterate over each character in the paragraph once.
- Create a Set from the banned words array. This adds O(m) time complexity, but allows for O(1) lookups on banned words.
- Create a Set of invalid characters.
- Create a Hash Map of encountered words with a value reflecting how many times the given word has occurred.
- Create a pointer at the beginning of the paragraph and iterate over each character.
- If a character is valid, add it to a word buffer, and move on to the next character.
- If a character is invalid or whitespace, consider what is in the buffer a word. Update the Hash Map to reflect the additional occurrence of that word then reset the buffer.
- Return the word that occurred the most.
Time Complexity: The solution creates a Set of all banned words, which takes O(m) time, where m represents the number of banned words. It also iterates over each character in the inputted string exactly one time, which takes O(n) time, where n represents each character in the string. This results in an overall time complexity of O(m + n).
Space Complexity: The solution creates a Set of all banned words, which will take O(m) space, where m represents each banned word in the array. It also creates a Hash Map of each encountered word, which will take O(n) space where n represents each character in the inputted string. This results in an overall space complexity of O(m + n).
/**
* Most Common Word
* 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.
*
* Time Complexity: O(m + n)
* Space Complexity: O(m + n)
*
* mostCommonWord('foo foo bar', []) // 'foo'
* mostCommonWord('Foo, Bar BAR!', []) // 'bar'
* mostCommonWord('foo foo bar', ['foo']) // 'bar'
*/
function mostCommonWord(paragraph: string, bannedWords: string[]): string {
let invalid = new Set(["!","?","'",",",";","."," "]);
let banned = new Set(bannedWords);
let words = new Map();
let buffer = ""
let result = "";
for(let ptr = 0; ptr < paragraph.length; ptr++) {
// character is valid, append it to the buffer
if (!invalid.has(paragraph[ptr])) {
buffer += paragraph[ptr].toLowerCase();
// unless it is the last character, end this iteration
if (ptr !== paragraph.length - 1) {
continue;
}
}
// character is invalid or is the last one
if (buffer) {
// if the word is not banned, increment it's count
if (!banned.has(buffer)) {
let occurrences = (words.get(buffer) || 0) + 1;
let mostOccurrences = (words.get(result) || 0);
words.set(buffer, occurrences);
if (occurrences > mostOccurrences) {
result = buffer;
}
}
buffer = "";
}
}
return result;
};