Dictionary tree (review)

Trie [traɪ] Pronunciation and try identical , Some of its other names are ： Dictionary tree , Prefix tree , Word search tree, etc .

Dictionary tree

It contains three words “sea”,“sells”,"she" Of Trie The appearance of ：

Defining classes Trie

class Trie {
private:
    bool isEnd;
    Trie* next[26];
public:
    // Insert 
    // lookup 
    // Prefix matching 
};

Insert

towards Trie Insert a word in word

Start with the child nodes of the root node word To match the first character of , Until there is no corresponding character in the prefix chain , At this time, new nodes are constantly opened up , Until the end of insertion word Last character of .

At the same time, the last node isEnd=true, It means it's the end of a word

void Trie::insert(string word){
    Trie* node = this;
    for (char c : word) {
        if (node->next[c - 'a'] == nullptr) {
            node->next[c - 'a'] = new Trie();
        }
        node = node->next[c - 'a'];
    }
    // Set the last node to isEnd=true, Indicates the end of a word 
    node->isEnd = true;
}

lookup

lookup Trie Whether there are words in word

Start with the children of the root node , Match all the way down , If the node value is null Then return to false.

If it matches the last character , Judge node->isEnd And back to .

bool Trie::search(string word) {
    Trir* node = this;
    for (char c : word) {
        node = node->next[c - 'a'];
        if (node == nullptr) {
            return false;
        }
        return node->isEnd;
    }
}

Prefix matching

Judge Trie Is there anything in the book to prefix Prefixed words

Be similar to search, There is no need to judge the last character node isEnd

bool Trie::startsWith(string prefix) {
    Trie* node = this;
    for (char c : prefix) {
        node = node->next[c - 'a'];
        if (node == nullptr) {
            return false;
        }
    }
    return true;
}

summary ：

1. Trie The shape of is independent of the order in which words are inserted or deleted , That is to say, for any given set of words ,Trie All shapes are unique
2. Find or insert a length of L 's words , visit next The maximum number of arrays is L+1, and Trie It doesn't matter how many words it contains .
3. Trie There is an alphabet in each node of , It's very space consuming . If Trie The height of n, The size of the alphabet is m, The worst case scenario is Trie Words with the same prefix don't exist in , So the spatial complexity is .

208. Realization Trie ( Prefix tree ) - Power button （LeetCode）

class Trie {
private:
    bool isEnd;
    Trie* next[26];
public:
    Trie() {
        isEnd = false;
        memset(next, 0, sizeof(next));
    }
    
    void insert(string word) {
        Trie* node=this;
        for(char c:word){
            if(node->next[c-'a']==nullptr){
                node->next[c-'a']=new Trie();
            }
            node=node->next[c-'a'];
        }
        node->isEnd=true;
    }
    
    bool search(string word) {
        Trie* node=this;
        for(char c:word){
            node=node->next[c-'a'];
            if(node==nullptr){
                return false;
            }
        }
        return node->isEnd;
    }
    
    bool startsWith(string prefix) {
        Trie* node=this;
        for(char c:prefix){
            node=node->next[c-'a'];
            if(node==nullptr){
                return false;
            }
        }
        return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

1804. Realization Trie （ Prefix tree ） II - Power button （LeetCode） 

Here we refer to an old brother's solution .. It breaks away from the traditional way of writing dictionary tree , Use a hash table to implement , Simple comparison

It should be noted that cnt+=it->second, instead of cnt++;

class Trie {
private:
    unordered_map<string,int>m;
public:
    Trie() {
       m.clear(); 
    }
    
    void insert(string word) {  
        ++m[word];
    }
    
    int countWordsEqualTo(string word) {
        if(m.count(word)){
            return m[word];
        }
        return 0;
    }
    
    int countWordsStartingWith(string prefix) {
        int cnt=0;
        for(auto it=m.begin();it!=m.end();++it){
            if(it->first.find(prefix)==0){
                cnt+=it->second;
            }
        }
        return cnt;
    }
    
    void erase(string word) {
        --m[word];
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * int param_2 = obj->countWordsEqualTo(word);
 * int param_3 = obj->countWordsStartingWith(prefix);
 * obj->erase(word);
 */