Most Common Word, by LeetCode

-

Problem is this one https://leetcode.com/problems/most-common-word/description/. String and Counting problems are (for the most part) solvable by using the string operators within your programming language (avoid reinventing the wheel, there is no need to do a lot of the parsing by hand anymore. If your programming language doesn’t support the basic string operations, time to switch languages) and hash-tables to quickly access specific substrings. This is exactly the approach that will be taken here. First a quick prep where we add the banned words to a hash-table and we also split all the words in the paragraph. Then it is just a matter of going thru the words in the paragraph, make sure they are not in the banned list, and keep track of the most common used so far. Code is below, Boris.

               public class Solution
               {
                              public string MostCommonWord(string paragraph, string[] banned)
                              {
                                             //Prep
                                             Hashtable htBanned = new Hashtable();
                                             foreach (string b in banned) if (!htBanned.ContainsKey(b.ToLower())) htBanned.Add(b.ToLower(), true);
                                             string[] words = paragraph.ToLower().Split(new char[] { ' ', '\n', '\r', '!', '?', '\'', ',', ';', '.' }, StringSplitOptions.RemoveEmptyEntries);

                                             //Process
                                             string mcWord = "";
                                             int mcCount = 0;
                                             Hashtable wordCount = new Hashtable();
                                             foreach (string w in words)
                                                            if (!htBanned.ContainsKey(w))
                                                            {
                                                                           if (!wordCount.ContainsKey(w)) wordCount.Add(w, 0);
                                                                           wordCount[w] = (int)wordCount[w] + 1;
                                                                           if ((int)wordCount[w] > mcCount)
                                                                           {
                                                                                          mcCount = (int)wordCount[w];
                                                                                          mcWord = w;
                                                                           }
                                                            }

                                             return mcWord;
                              }
               }

Comments

  1. TarasMay 21, 2018 at 11:42 PM

    As always, sharing a simple solution for a simple problem:

    import collections

    class Solution:
    def mostCommonWord(self, paragraph, banned):
    banned = set(banned)
    return next(word for word, _ in collections.Counter(word.rstrip("!?',;.") for word in paragraph.lower().split()).most_common() if word not in banned)

    Note really a one liner, but fairly close :) A more efficient implementation can use a Trie to store words of the paragraph and banned words. Storing paragraph words in a trie would make increments and checks for banned words O(k) where k == len(word), but oh well :)

    Cheers,
    Taras

    ReplyDelete

Post a Comment

Popular posts from this blog

Count Binary Substrings

-
Image
Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
Read more

Count Vowels Permutation: Standard DP

-
Image
Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
Read more

Maximum Number of Balloons

-
Image
#431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
Read more