leetcode

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;
};

more LeetCode posts