力扣-208题实现Trie（前缀树）（C++）- 字典树+有价值

浅浅的花香味﹌ 2022-09-16 12:22 159阅读 0赞

题目链接：[https://leetcode-cn.com/problems/implement-trie-prefix-tree/][https_leetcode-cn.com_problems_implement-trie-prefix-tree]  
题目如下：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16 1]

class Trie {
        
    public:
        struct Node{
        
            Node *son[26];
            bool is_end;
            Node(){
        
                for(int i=0;i<26;i++)
                    son[i]=NULL;
                is_end=false;
            }
        }*root;
    
        Trie() {
        
            root=new Node();
        }
        
        void insert(string word) {
        
            auto p=root;
            for(auto ch:word){
        
                int pos=ch-'a';
                if(p->son[pos]==NULL) p->son[pos]=new Node();
                p=p->son[pos];
            }
            p->is_end=true;
        }
        
        bool search(string word) {
        
            auto p=root;
            for(auto ch:word){
        
                int pos=ch-'a';
                if(p->son[pos]==NULL) return false;
                p=p->son[pos];
            }
            return p->is_end;
        }
        
        bool startsWith(string prefix) {
        
            auto p=root;
            for(auto ch:prefix){
        
                int pos=ch-'a';
                if(p->son[pos]==NULL) return false;
                p=p->son[pos];
            }
            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);
     */

[https_leetcode-cn.com_problems_implement-trie-prefix-tree]: https://leetcode-cn.com/problems/implement-trie-prefix-tree/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/4febe090b8f643988c9df8528b5420e7.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/4c593c62fb0e49748c7f0af17eadabb7.png