面试题 16.02. 单词频率

面试题 16.01. 交换数字

hashmap

class WordsFrequency {
public:
    WordsFrequency(vector<string>& book) {
        for(auto& b : book)
            ++map[b];
    }
    
    int get(string word) {
        return map[word];
    }
private:
    unordered_map<string, int> map;
};

/**
 * Your WordsFrequency object will be instantiated and called as such:
 * WordsFrequency* obj = new WordsFrequency(book);
 * int param_1 = obj->get(word);
 */

字典树(前缀树)(Trie)

class WordsFrequency {
public:
    WordsFrequency(vector<string>& book) : root(new Node()) {
        for(auto& b : book)
        {
            auto pt = root;
            for(auto& ch : b)
            {
                if(!pt->childs[ch - 'a'])
                    pt->childs[ch - 'a'] = new Node();
                pt = pt->childs[ch - 'a'];
            }
            ++pt->f;
        }
    }
    
    int get(string word) {
        auto pt = root;
        for(auto& ch : word)
        {
            if(!pt->childs[ch - 'a'])
                return 0;
            pt = pt->childs[ch - 'a'];
        }
        return pt->f;
    }
private:
    struct Node 
    {
        Node* childs[26];
        int f;
    };
    Node* root;
};

/**
 * Your WordsFrequency object will be instantiated and called as such:
 * WordsFrequency* obj = new WordsFrequency(book);
 * int param_1 = obj->get(word);
 */