1454. Word Frequency Count

Description

中文English

Input a string s and a string list excludeList to find all the most frequent words in s that do not exist in excludeList. Your results will be sorted by lexicographic order by online judge.

• The words are case-insensitive and finally return lowercase words
• Non-alphabetic characters in the string are considered as spaces, and spaces are word separators
• The length of all words does not exceed $10^5$ and the length a word does not exceed $100$

Have you met this question in a real interview?  

Example

Example 1:

Input：s="I love Amazon.", excludeList=[] 
Output：["i","love","amazon"]
Explanation:
"i", "love", and "amazon" are the words that appear the most.

Example 2:

Input：s="Do not trouble trouble.", excludeList=["do"]
Output：["trouble"]
Explanation:
"trouble" is the most frequently occurring word.

Code(Language:C++)

class Solution {
public:
    /**
     * @param s: The string s
     * @param excludeList: The excludeList
     * @return: Return the most frequent words
     */
    vector<string> getWords(string &s, vector<string> &excludeList) {
        // Write your code here
        vector<string> res;
        const int size = s.size();
        if(size == 0){
            return res; 
        }
        map<string, int> cnt; 
        unordered_set<string> exSet; 
        for(auto i : excludeList){
            exSet.insert(i); 
        }
        int i = 0; 
        
        while(i < size){
            while(i < size && !(s[i] >= 'A' && s[i] <= 'z')){
                i++; 
            }
            if(i == size){
                break; 
            }
            int start = i; 
            while(i < size && s[i] >= 'A' && s[i] <= 'z'){
                i++; 
            }
            string word = s.substr(start, i - start); 
            string lowW = toLow(word); 
            if(exSet.find(lowW) == exSet.end()){
                cnt[lowW]++; 
            }
        }
        int maxFreq = 0; 
        for(auto i : cnt){
            maxFreq = max(maxFreq, i.second); 
        }
        for(auto i : cnt){
            if(i.second == maxFreq){
                res.push_back(i.first); 
            }
        }
        return res; 
    }
    string toLow(string &s){
        for(int i = 0; i < s.size(); i++){
            if(s[i] >= 'A' && s[i] <= 'Z'){
                s[i] = (char)'a' + s[i] - 'A'; 
            }
        }
        return s; 
    }
};