Implement Trie (Prefix Tree)（C++实现 Trie (前缀树)）

雨点打透心脏的1/2处 2022-09-02 00:47 144阅读 0赞

（1）多个子节点

class Trie {
    private:
        vector<Trie*> v;
        bool isend;
    public:
        Trie* search_prefix(string word) {
            Trie* node=this;
            for(int i=0;i<word.length();i++) {
                int index=word[i]-'a';
                if(node->v[index]==nullptr) {
                    return nullptr;
                }
                node=node->v[index];
            }
            return node;
        }
        /** Initialize your data structure here. */
        Trie():v(26),isend(false) {
            
        }
        
        /** Inserts a word into the trie. */
        void insert(string word) {
            Trie* node=this;
            for(int i=0;i<word.length();i++) {
                int index=word[i]-'a';
                if(node->v[index]==nullptr) {
                    node->v[index]=new Trie();
                }
                node=node->v[index];
            }
            node->isend=true;
        }
        
        /** Returns if the word is in the trie. */
        bool search(string word) {
            Trie *node=search_prefix(word);
            return node!=nullptr&&node->isend==true;
        }
        
        /** Returns if there is any word in the trie that starts with the given prefix. */
        bool startsWith(string prefix) {
            Trie *node=search_prefix(prefix);
            return node!=nullptr;
        }
    };
    
    /**
     * 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);
     */